Locked out of Linux VM after using `gcloud compute os-login ssh-keys add`

Just like this guy, I started getting an error message when trying to add ssh keys:

Supplied fingerprint does not match current metadata fingerprint

I get this error when I try to add the keys to

• the specific VM instance details (using web interface)
• the shared metadata (using web interface)

I also get Permission denied (publickey). no matter if using username@instance or username_mycomp_com@instance to login. I and all of my colleagues can also no longer use the ssh web login, meaning we have been locked out of our own server!

I can only attribute this to running the gcloud compute os-login ssh-keys add command, which seems to have affected more than it says.

Other commands that might have affected this issue

gcloud compute ssh

$ gcloud compute ssh dev-mycomp-no
WARNING: The public SSH key file for gcloud does not exist.
WARNING: The private SSH key file for gcloud does not exist.
WARNING: You do not have an SSH key for gcloud.
WARNING: SSH keygen will be executed to generate a key.
Generating public/private rsa key pair.
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
Your identification has been saved in /home/carlerik/.ssh/google_compute_engine.
Your public key has been saved in /home/carlerik/.ssh/google_compute_engine.pub.
The key fingerprint is:
SHA256:cicl5t/5mDmIocrkDopK2C6Rf9OvT7FhKAh9GEMPFd8 carlerik@ubuntu
The key's randomart image is:
+---[RSA 2048]----+
| .=.o.           |
| . * . .         |
|. o o . E .      |
| . o   + o       |
| .. . o S .      |
|+.   . +.B . .   |
|.+o .. .oo..o    |
|+o.=o o.. . .=   |
|=..o=o.+o   +..  |
+----[SHA256]-----+
No zone specified. Using zone [europe-west1-b] for instance: [dev-mycomp-no].
WARNING: Using OS Login user [carlerik_mycomp_com] instead of default user [carlerik]
Warning: Permanently added 'compute.7727415340568554709' (ECDSA) to the list of known hosts.
[email protected]: Permission denied (publickey).
ERROR: (gcloud.compute.ssh) [/usr/bin/ssh] exited with return code [255].

gcloud compute os-login ssh-keys add

gcloud compute os-login ssh-keys add --key-file ~/.ssh/id_rsa.pub  | stack-overflow 
    loginProfile:
      name: '111200762294302015941'
      posixAccounts:
      - accountId: charged-foo-162409
        gid: '438632669'
        homeDirectory: /home/myuser_mycomp_com
        operatingSystemType: LINUX
        primary: true
        uid: '438632669'
        username: myuser_mycomp_com
      sshPublicKeys:
        f7fd01c562d4edb7292eada91dfb2213ef2344f9db605eedc65ac08cea39327e:
          fingerprint: f7fd01c562d4edb7292eada91dfb2213ef2344f9db605eedc65ac08cea39327e
          key: |
            ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQCtB10ag2fipH7Cnls3gZvl5eBJx0OvQaLu7hndL5sif3m4CTGmrN/MuP0lei0Rt23cBy5Ey2DqAjmizCAhdc3jSQm0pXisKG92Juo2HxiJw+eMUucoPhjbEy35sKKrru2//5uPpK5IEeVEve3bIXCAQUQgyOESmHBgXmKSCz0jQXEvcV8GxxkdXK7/UQVSe5wtxzPHOoP+foobar+bjHXnQkiqk5oDeP3ewPorrvxbOeOcqk0b1qrAQYSXHqXv6lENfWIceIz1EsZlRsIV i9-mycomp

gcloud compute instances add-metadata the-instance --metadata enable-oslogin=TRUE

Saw this in a guide. Assumed this would enable additional ways of logging in. In hindsight, I see I have no idea what this does.

Debugging info

$ gcloud compute os-login describe-profile  
    name: '111200762294302015941'
    posixAccounts:
    - gid: '726506529'
      homeDirectory: /home/myuser_mycomp_com
      operatingSystemType: LINUX
      primary: true
      uid: '726506529'
      username: myuser_mycomp_com
    - accountId: foo-mission-162409
      gid: '438632669'
      homeDirectory: /home/myuser_mycomp_com
      operatingSystemType: LINUX
      primary: true
      uid: '438632669'
      username: myuser_mycomp_com
    sshPublicKeys:
      3573aef91758f9706a884bffc95502ea5f31bbfab7a33d58be8abd9a84f53808:
        fingerprint: 3573aef91758f9706a884bffc95502ea5f31bbfab7a33d58be8abd9a84f53808
        key: ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQDCaISFI0hCDMK5SIqIBlsboBQTBCoW98bvjUjoCDn9S4kXSOtVvwNeXc/Kb+9lXqKR8CbtYgOZySPqI+5VADdAIcfot2S65Fq5qOQ1IH7Uo29nzvhyjfRbckAs3gaTF6uzxEA0THqyAZ1oGIyK3vDI8W/Ofczi08oIYWpMmWA8dQNQuKRujloDuFElpjZEjbEyfkn/e7iSm1VxZ8aLEw7M3/BsJLmtwxa+tYyTAfKx63NRFbSWf873GLOyAKCnE5ls27ftlTjDJMISI3RZd1KMdyg+6KAwN7YsCTwJXarNXr9v2GcY8lrpC7dQ/lGK1nBsPa0kOSYKQzJ0LIDxfOan
          myuser@ubuntu