If you are rooted and have ClockworkMod recovery, you can try these steps:

1. Uninstall Google play services.
2. Boot into recovery and select "wipe data".
3. Then select "clear cache".
4. Then select "advanced" and in the sub-menu select "wipe dalivk cache".
5. Then go back and select reboot.

Now the Play Store will start working.