I have the same problem. My phone is an LG Optimus 2X running Gingerbread 2.3.4. noticed it about two weeks ago, Did a factory reset, and all was good - until I went on the Play Store to redownload my apps, Play Store updated itself from 3.4.7 to 4.9.13. The problem reappeared. Uninstalling the update from Applications resets Play Store back to Play Shop, but if I go into it again, it auto-downloads the update again.
How widespread is this - I googled at the time, and no-one was reporting it.
I don't have the box checked for unknown sources enabled, and the only 'non-corporate' apps I have on the phone are:
Battery Mix, eBroadcast, Equalizer, Swype + Dragon, and TransitTimes+. To rule out any conflict, have you got any of these installed?