Depending on how far you are willing to go, if you've rooted your handset you could install a terminal and check if you do a full trace route to google (command is "traceroute http://www.google.co.uk"). If it's a DNS issue then it's either ongoing (as rebooting flushes your DNS cache) or 3 made a mess of their DNS or possibly NAT.
That's a good idea. Funnily enough, it worked yesterday, I'll see what happens today. Anyone else able to try this?