Did you ever get this resolved? I have the same issue. I connect to my WiFi. I can browse the internet, but it just won't connect to the store no matter how many times I reboot the thing. I've also tried it over different WiFi connections and still get the exact same error message. I'm hesitant to Factory Reset the thing cuz I'll lose all my gamr progress.