Just in the past few days I've seen several machines that can't get anywhere on the internet, through either Internet Explorer or Firefox.
The thing in common was AVG 8.0 so I did some investigating. Turns out, the Webshield / Surf Protection had become corrupt, and was preventing the browser from going to any web site.