Go to Settings --> Applications --> All --> Google Play Store
In there I uninstall updates, clear data and clear cache.
Run Play Store App and update it.
If you have other solutions, please post them here. I understand it's kinda tedious to wade through all the threads looking for a specific fix you read a long time ago.