When adding SSH keys to Google Cloud Console (GCC) instances I ran into the problem that even after adding my public key to it I couldnt connect.
After searching around some and not being able to find a solution, I tried to change with the pubkey comment to my GCC instance username.
This finally solved my connectivity issues.
For the most part, the Documentation provided is very helpful and extensive, but what it fails to mention, is that the comment on the public keyfile seems to be expected to be the GCC instance username.
To fix this, simply add your public key as described, but before saving it, change the comment to match your instance username.
This works both for project level keys added through metadata and for instance level keys added through Instance->Edit->SSH Keys