There is no linked app associated with this client ID

I had the same issue. All you need to do is to make sure before creating a new game, you input the exact package name and the fingerprint certificate (SHA1) that matches your release keystore. My problem is that I put a default fingerprint in the game and decided to change it later. Somehow the google console developer can still detect your previous fingerprint even though you replace it with your final fingerprint. The solution was to delete the first game configuration and created a new one. No need to create or attach your debug certificate.

Is Game Services published in the Google Developer Console? That's a separate step.

If your app itself isn't published (i.e. in beta), only those google accounts associated with a specified google+ or google groups account designated to be your pool of testers will be able to connect.

You also need to verify that the app_id compiled into your app (often in /res/strings.xml) matches the google api console ID. For example there should be a line like:

<string name="app_id">123456789123</string>

And don't get it confused with your facebook application_id!

Beyond that you'll need to check the Google Cloud Console under Overview -> APIs & auth -> Registered apps and verify that the prefix for CLIENT ID matches, that the PACKAGE NAME is correct, and the CERTIFICATE FINGERPRINT (SHA1) matches.

If it doesn't work after all that, you'll be roughly where I find myself currently-- having done all that and still stuck.