Your encrypted data is locked on this device

I got a new phone and when trying to use or create a passkey, I was presented with the error:

Your encrypted data is locked on this device

For security, you can no longer access your encrypted data on this device. Try again using a device you've recently used to sign in to your Google Account. 

Visit g.co/OnDeviceEncryption to learn more.

I still had my old phone and hadn't wiped it yet. Surprisingly, I was getting the same error on the old phone as well.

The Device Encryption page linked in the error message is very generic and completely unhelpful. 

I tried a lot of things, clearing cache etc, the usual troubleshooting. In the end, what made it start working was to log into my google profile in Chrome on a computer and run the safety check (the thing that searches all your saved passwords for possible problems.)

After running that check on my computer, passkeys magically started working on my phone...