I just updated my Nexus 10 to 4.3 and whenever I try to download something from the Google play store I get this message. And I accidentally cleared the data for Google play services.
I also have the same problem. I cleared the Google Services Framework to get JB 4.3 OTA to install. The problem began after that. I tried the force stop and log out then log in on the Google play service. That didn't fix it.
Had the same issue as OP and did this and it worked. Funny thing is the framework thing didn't get me the update sooner, but I got it when I got home from work anyway... Impatience...
I had the same problem. I had to delete my google account, stop framework, appmstore and clear cache and data from both, re add the gmail account, then reboot.