I am currently using Play 3.5.15 and the issue persists after repeated reinstalls of play (I also tried an older Market install which did the same thing). Any help greatly appreciated with this.
I don't have a full explanation but the issue is resolved. I installed a root explorer and over wrote the Vending.apk with the in /system/app, I cleared play app data and tried again. That didn't makea but of difference. Magically I tried running play a few hours later and it worked. Possibly a server side issue then? Hopefully it's resolved for everyone now anyone.