What worked for me (on a rooted Galaxy Ace) was to copy the folder with full path where GPlayStore--com.android.vending.apk--resides, /system/app, to my SD card, then I uninstalled it. It seems that if that file is detected anywhere in the phone, whatever auto-installs it got so fooled that I had a hard time reinstalling it, until I reinstalled it from my SD card again. I copied the entire folder to my SD card and later to my PC, just in case I got overzealous and went overboard uninstalling stuff, or if something else needed to be reinstalled before or after GPStore. (I think I had to reinstall GPServices.)
NOTE: Your phone must be rooted, and don't forget to create a System folder on your SD card and copy the App folder within.
In order to uninstall it, I used Link2SD, converted GPStore to User App, then uninstalled. To reinstall, as said before, did so from the SD card and converted it to System App. The last conversion is no necessary, unless you want to bring the phone back to "original".
Hope this helps.
Cheers