I'm having similar problems. I'm running Vista.
My laptop is connected to the net using a router but I cannot view web pages using Explorer. Windows Live Messenger works fine as does my PS3 so it's not a router/connection problem.
Firefox does not work as well as I have already tried that remedy. I also updated and downloaded IE8 which also doesn't work. Any help would be great!!