Since different users have reported different "fixes" resolving the issue (fixes which don't work for others), I have to agree with the above post that there is more than one root cause. A quick summary of various fixes seen in this thread and elsewhere:
- changing your primary Google account password
- force-stop and clearing cache/data on Google Services Framework, Play Store, and/or Google Play Services
- wiping cache/Dalvik
- removing and re-adding your Google account(s)
- uninstalling Play Store updates
- updating Google Play manually, e.g. with downloaded APK
- turning off sync / turning off WiFi/mobile data
- ROM reflashes or factory resets
- various combinations of the above, usually with reboots in between
For me, I tried everything above except for reflashing/resetting, and a manual installation of the latest Play Store apk was what finally resolved it. I have no real evidence, but I suspect a pushed Play Store update may have interacted badly with XPrivacy in my case - and although XPrivacy could query for allow/deny on usage, I could not change permissions for Play Store within the XPrivacy app. In other words, it might not be that updating Google Play fixed it so much as the update forced XPrivacy to re-query about all permissions...and this time when in doubt I clicked "Allow." YMMV, but I'm hoping this makes troubleshooting easier for somebody out there than it was for me.