1. Delete your account at https://account.services.mozilla.com
2. Recreate it with the same username and password, but be careful to get the "Sync Recovery Key" from the "Manage Account". The interface is a little odd, because it's assuming you want to change the key, not copy it. On the panel select "Cancel" after you have copied the key to a warm, dry place.

3. Went to my new device and started the process to pair the device. Then it all worked. Good luck.