I can't browse to any website using Safari yet Google Chrome is working fine. The Mac App Store also reports that it cannot connect.
Running OSX 10.7.2 on a 2011 MacBook Pro.
As we have found the solution using Comments, here's the formal response.
Whenever you experience issues with Safari, App Store, iTunes and any other service that uses the "same" WebKit, but seem to see no problem in Google Chrome or Firefox, it's good to check if you have your Proxies configuration clear. Since sometimes Chrome (and Firefox) override these settings (for their own multi platform stuff), they may work while the formers fail.
This is easily checked by opening Safari -> Preferences -> Advanced -> Proxies (Change Settings).
Make sure Autodiscover is not checked. It should probably look all empty like this:
note/off-topic: the Use PASV FTP is usually a good idea if you are behind a router/modem/NAT like Airport Extreme or AirportExpress (or any other to be honest), since FTP was not designed to be used behind these "hacks". In any case, if you don't know what it is, you can safely ignore it, but if you have FTP problems every now and then (or FTP is slow as hell), check that and try again.
The local ignores for proxies was added by the Operating System, but it's usually a good idea to have your local stuff ignore the proxy. ;)