In my case, the problem was that I had created a new Google account but had forgotten to register it as a tester in Google Play Console. Because I am debugging my app, the account doesn't "just work" - it has to be a registered test account.

I went to Google Play Console: Play Games Services | Setup and management | Testers and added the email address. Now it works fine. Got to say though: it wasn't the most helpful error message.