An updated version of Google's Play Store was released today, version 5..12. 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.5.8.apk
now over 900,000 downloads since the thread opened!
The attached APK is installable just like any side-loaded APK. Or if you are rooted, you can move the APK to /system/app (or if you are on KitKat, to /system/priv-app) 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.
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.