Try this:
Go to Control Panel, Internet Options, click on the Connections tab; select 'Never dial a connection' and click Apply; then click the LAN Settings button and uncheck all the boxes, OK and Apply .
Try IE again. If it still doesn't work, go back to the LAN Settings and try it with 'Automatically detect settings' checked and Applied.
Sorry for the extreme bump but I've been trying to figure this out for forever now. I'm on 7 (7057) and it's been just like this. Firefox works, aim works (upgraded last night to the current beta and everything) but IE would not connect, nor would Y! Messenger. Thank you soooooooooo much for this, as typing in "can't connect to IE but can connect to firefox" brought this page as the first result, so yeah.... thanks again. :D