Play Store/Market Not Working?

I noticed a lot of old and new posts with issues regarding the Google Play Store not working. I think it's a good idea to start a thread where we can post and consolidate all our fixes. Here's what I do when I encounter the play store bug:

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.