I think I may have an answer (just from my obsverations anyway).
I started getting the same error about a month ago on either WiFi or 3G. Rebooting wouldn't help at all. It went away but then happened again this week.
On my home internet, I use OpenDNS as my DNS server, as I find it faster than my ISP's DNS server.
Considering Android market probably has servers all over the world, possibly my phone was getting a wrong server IP because I was using a DNS server from another country.
So I changed my DNS server to googles public DNS server (8.8.8.8), and after I rebooted my phone, the problem went away!
The reason why it wouldn't work with 3G either is because my phone connects to WiFi first and it caches the DNS record of the market server and probably requires the local server in the country you reside.
Hope that helps for some people!