1) Be sure, your phone is rooted properly
2) Download Root Explorer if you don't have it installed
3)Go to /system/app/ and delete the Vending.apk (Phonesky.apk for ICS 4.x.x) (leave the Vending.odex untouched!). Make sure you have an backup your old Vending.apk (Phonesky.apk for ICS 4.x.x) to your SDCard as well.
4) Install the downloaded Vending.apk (rename it to Phonesky.apk if you have ICS 4.x.x)
5) Reboot your phone
6) Start Play Store and grant the access. You'll be asked to do so
Edit: there is a com.android.vending-2.apk in my /data/app/ though. Not too sure why it's there, but I reinstalled the original .16 backup I had.