Possible solution:
- Make sure you are using the latest version of Google Play Service & most importantly your Play Services isn't disabled. You can download the latest version here,
https://play.google.com/store/apps/details?id=com.google.android.gms
Uninstall any previous updated before installing the new one
Goto -> Settings -> Apps -> Google Play Services -> Uninstall installed updates
- Make sure your current date/time is correct.
UPDATED ANSWER:
If you are using an emulator you should keep in mind that emulator doesn't support Google Play Services by default. What you can do is download and install Google APIs from SDK Manager then create a new device in emulator using the Google APIs as target.
First install Google APIs from SDK Manager,
Create a virtual device like this,
For Android Studio,
For Eclipse,