Im getting this same problem, i can watch youtube videos super fast, and most of the time the internet, but when i go into market or update facebook, i get the same error of check your internet connection. Ive tried free wifi and it works great, i just got this linksys wirless g router, and i have only my laptop and wii(rarely used) using the wifi, everything else is hardwired. I do use Wifi Analyzer to connect and i also run Speedtest.net and get 6.0 ish download 1.0 upload. Any help, im kind of new to wifi. It is password protected and secured with WEP.
Ended up being a problem with my cable from my modem to my router, it was having bad connectivity issues, got a new cable now it works fine.