Nevermind.
I tried entering an older recovery key and got the failed to recover with that key error. Then I re-entered the “correct” key and was able to continue. I’m working now.
And I know this totally sounds like a typing error on my first attempt, but I swear that I compared every set of six digits of the recovery key multiple times.