I'm having the same issues with my GSM Nexus S on T-Mo. Running 4.1.1. This is just maddening. I've rebooted several times, but no dice. I've been deleting apps all over the place at first, thinking the error message was legitimate. Of course, after a while, I realized what was going on. Actually, while I was typing this, I checked my phone, and Google Maps, one of the apps that was giving me this error seems to have updated, but several other apps are still giving errors.