This method works only if you are rooted and have Clockworkmode recovery.
Follow these steps:
1-Uninstall Google play services.
2-Boot into recovery and select wipe data.
3-Then select clear cache.
4-Then select advance and in it select delvik cache.
5-Then go back and select reboot.
All Done!!
Now the google play store will start working.