I've had the same with a Galaxy Nexus on 4.1.2. I think what caused it was my stopping the Google Services Framework and clearing the data so that I could do a proper, clean check to see if 4.2 was available (it wasn't) without doing a manual install.
I really didn't want to follow the guide above in deleting my account because it's the primary account and it would effectively reset the phone and mean a lot of work to get it back as it is.
I did fix it, however. What I did was the following:
- Create a new Google account with any name you choose. It's temporary, so pick anything
- Clear dada & cache for the Google Play Store
- Uninstall updates for Google Play Store, taking it back to the factory installed version (don't worry - you'll get the updates back)
- Start Google Play
- Select accounts and choose the new one you've just created
- Go to My Apps and pick (a free) one to update and update it. That should be successful
- Come out of Google Play
- Go into settings and delete the temporary Google account you just created
- Go back to Google Play and make sure that the account is set to your primary one
- Complete all updates
All should be well. But - it may be very different for you than it was for me. Anyway - this is all non-destructive, so it's easy and painless to try.