Are you using Zone Alarm? If so check the box for "Allow outgoing DNS/DHCP in the trusted zone"...
If not, it may still be a DNS problem. When you can't connect in IE, if you type
http://216.239.39.99 in the address bar can you connect to Google?
If you can, try ipconfig /flushdns and ipconfig /registerdns in a command window in case your dns cache is corrupt...