Fixed it 20 minutes ago.
It's still very weird, and shows how inconsistent the whole Google Play system can be sometimes.
Tons of people had similar issues using the Google API.
In my case, the issue was more or less like this:
1. When I created the first iteration of Space Haze, I made a mistake somewhere along the line, and Autho0/Credentials/SHA1/Linked Apps combo was somehow messed up, probably because I might have created a new client ID for my game from the Google API console, which is apparently a no-go, although you can do it.
Google says the following about that issue:
"Warning: Do not create new client IDs for your game from the Google API Console. If you do so, Google Play games services will not associate your game settings with the client ID, and this could cause errors during gameplay."
2. Some hours later, I set up a new LINK in the Game Services Tab ( you can't delete old links. DOH ) and RENAMED the old one. ( I chatted with the Google tec team several times, but they didn't know crap and couldnt do shit ).
3. I somehow managed to delete all the crap in the Googe DEV console that didnt work and that I wasnt supposed to be able to delete. DOH again....
4. Before they revamped Google Play DEV console, SHA fingerprints changed with each new version you uploaded, and you had to use the same fingerprint in the game services AND in the app package credentials. Or whatever the name is. Which was no problem, you could have it displayed in game services tab and copy/paste it.
5. Achievements worked fine at some point. Leaderboard didnt. Couldnt find the problem, but the Leaderboard was of little concern to me. I ignored it.
6. After the revamp, I occasionally updated Space Haze, and the achievements sitll worked, although I didn't change the SHA1 anymore ( because it wasnt possible to have it displayed in game services anymore ).
7. Google+ died, TGC updated the Google API, I updated Space Haze with the new API commands and uploaded it. Achievements didnt work anymore.
8. Tried everything as described in the previous post, nothing.
9. So I used the Java keystore tool to generate a new SHA1 fingerprint and replace the old fingerprint in the credentials with the new one I just generated ( for the first time ).
10. No way, The fingerprint you specified is already used by an Android OAuth2 client ID in this project or another project. Crap ^^
11. Somewhere DEEP in the Google Cloud Platform, I found remains of my first Space Haze Project. Checked the fingerprint, it was the same I just generated.
12. Set it to 00:00:00:00................
13. Repeated Step 9 ---- > SUCCESS. Could replace the SHA1 fingerprint.
14. Unpublished app, unpublished game services, republished game services, republished app ( in that order )
15. Reinstalled Space Haze, created new Play Games profile
16. ACHIEVEMENTS WORK, LEADERBOARD WORKS FOR THE FIRST TIME
17. Open Beer