Go to Settings --> Applications --> All --> Google Play Store
In there I uninstall updates, clear data and clear cache.
Reboot
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.
— modified on Oct 15, 2012, 6:54:38 PM