Did the following and it worked for me on the Galaxy S3 (stock rooted):
Uninstall updates for Google Play Store
Clear cache/data and force stop Google Play Services, Google Play Store and Google Services Framework
I briefly ran into "no connection" errors with Play Store after it updated itself...