An updated version of Google's Play Store is now available, version 8.1.31.S-all. 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. 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).
DOWNLOAD >> PlayStore_v8.1.31.S-all.apk
Now over 1,000,000 total downloads since the thread opened, I'm done counting
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.