An updated version of Google's Play Store was released today, version 5.8.11. The new APK is linked below; it is not themed or modified in any way. It should work on any version of Android in any part of the world.
DOWNLOAD >> PlayStore_v5.8.11.apk
now over 1,000,000+ total downloads since the thread opened! I'm done counting
The attached APK is installable just like any side-loaded APK. Or if you are rooted, you can move the APK to the appropriate /system folder manually or with a flashable zip to replace your existing Play Store (Phonesky.apk or Vending.apk).
Screenshots are linked from Android Police, I won't pretend like I can create a nicer and more comprehensive collection of all the various pages.
Older versions of the APK are still attached just in case you're weird like that; however you will need to modify the old versions to prevent auto-updating, otherwise you will eventually end up on the latest version.
NB: Just to ease everyone's mind, don't be alarmed by the posts directly below this. @DJxSpeedy and I were trying to figure out some of the new folders and permissions when version 3.10.9 was released and before it hit the mainstream, but that has since been explained by Android Police.