Try uninstalling and re-installing Google Play Game Services. Use this URL in Chrome on your device, and open the link with the Play Store app to get to it:
https://play.google.com/store/apps/details?id=com.google.android.gms
From the store, you can uninstall it, and then it will automatically reinstall itself when you start any game (like ours) which uses Google Play Game Services.
(Please note that you must be playing with a licensed version that you purchased and downloaded through the Google Play store. Other versions of the game will not allow sign in.)