Is MSN your ISP?
I had the same thing happen today after work. I could connect to work, and then going through the network there, connect to the internet (using my MSN connection), but I would get 'server not found' every time I tried to hit a site normally. I finally clicked 'Detect Network Settings' in the error message, which seemed to make it actually check my network settings, and it worked fine.