The problem may lie in a subtle misconfiguration in IE that not many people run into a lot, but which does affect your connectivity in some cases. In IE, look under Tools | Internet Options | Connections | LAN Settings, and make sure the "Automatically detect settings" box is unchecked. When checked, this option forces IE to look for a local web proxy -- which doesn't exist most of the time, and is a giant waste of effort on the computer's part.
Another thing to look into is the system's HOSTS file, a plaintext file in the directory %SystemRoot%\system32\drivers\etc. This file holds a list of quick-lookup values for network addresses. If there is an entry for google.com (or any google.com subdomains) in there, delete them and save the file; the references may have been installed by third-party programs and may not be valid.
This was first published in September 2004