This issue seems to be account-specific, and the only known solution so far is to make a new Google account. My guess is that the players affected were playing the game when something happened (Google Play Services updated?), and now they are still marked as playing that game. So, they can't start a new one. The corresponding issue is here:
https://code.google.com/p/play-games-platform/issues/detail?id=70
Update: Google team has marked it Fixed.