I had something like this and the DNS Client (it turns URLs like http://www.google.co.uk into an IP address) was not running for some reason.
If the FlushDNS thing doesn’t work
Try checking that the DNS Client is running:
Start->Administrative Tools->Services
Find DNS Client. If the status column doesn’t say Started this could be your problem. To fix:
Right Click on DNS Client and select properties.
Change Startup Type to Automatic.
Click Ok
Right Click on DNS Client again and select Start
Now try the browser. You may need to restart the browser first.