After you have updated SHA-1 on the API Console, you may need to uninstall and install again the app.
Seems like Google Play Services is keeping "unauthorized" answer from the server in cache.
Edit:
You can try creating another API key without specifying SHA and package name. This will create a key that says "Android apps: Any app allowed". I'm a bit concerned about such possibility, because that key could be used by anyone in their apps, but for development it is not an issue.