Are you adding the correct ID? It should be similar to this: https://developers.google.com/games/services/images/consoleLocationOfApplicationId.png
Do you use Android Studio? I had the same problem, (only with Gameservice) sign the app with Android Studio without errors-> App crash after start sign the app with Eclipse with lot of errors-> App works fine i don't know why but this was my Experience
I just saw that very time that im rendering my game on Eclipse my game crashing (with Gameservice and without)