Can you connect to google if you type in
http://209.85.229.99:80 (IP and port for Google.co.uk) ? If so it is a aidnjt says, almost certainly a DNS error. If not, then it may b3e a firewall problem, either in your version of Windows, an add on firewall application, or your router. You might also want to try doing a tracert to
www.google.co.uk - the first line should show the DNS resolution google.co.uk but as tracert uses a different protocal (ICMP) and that gives a little more info to help diagnose the problem.
It is strange that the system worked for a short tuime after a re-install... Did you add or change anything during that time? And who is your ISP? Are there any other computers attached to the router? Do they work or not?
Nightkhaos - I'm not sure that aidnjt has a particularly advanceed knowledge or not, but his suggestion of a bad DNS record is still a valid one and worthy of consideration, however unlikely you may consider it to be!