If you already have an internet connection try getting the IP address of the URL's you've just listed, I.E the IP address for www.google.com
is 220.127.116.11. There will be some shitty DNS look up tool on the web floating about somewhere
Try doing a few pings to the ip addresses of the sites you're having trouble with, if its not good try a traceroute.
Post back your results!
EDIT - ah, you can access these via proxy? Still traceroute the URL's from your machine command prompt