Alright, came across something else to try:
Open System Preferences (under apple menu) and click on "Network". I want you to check two things:
1) Is the "Location" (top-most option above "Show") set to "Automatic" or something else?
2) Double Click on the option in the lower part that you're using to connect to the internet (it'll have a green light next to it if it's connected) then click on the TCP/IP tab and see what DNS servers you have. You may need to contact your ISP to verify that they're correct or haven't changed (most people shouldn't have anything in this field, or the "Search Domains" field)
I'm intrigued by your problem. If you stumble across anything, do let me know.
P.S. - Open Safari, and under the "Safari" menu, choose "Empty Cache" (or hit Command+Option+E) see if that doesn't help.