"Unable to read some of your folders" / "Conv. Rekeying required"

Moved from https://github.com/keybase/keybase-issues/issues/3074

I connected 2 new computers and validated them with my phone. One of my conversations now says I need to rekey it. Upon pressing I see

The Moto device is however turned on and the chat is available on that.
I saw the same message box on the other computer. Upon entering a paper key they disappeared.. at first... actually let me bring some order in the events that happened:

• Install keybase on device "Toliop"
• Install keybase on device "edox"
• Verify "Toliop" using "Moto"
• Verify "edox" using "Moto"
• See pictured msg box on both new devices
• Create Paper Key on "moto"
• Enter Paper Key on "Toliop" and "edox"
• Box disappears on both
• Click on private conversation on "Toliop"
• See "REKEY NEEDED" next to the user name. Conversation itself not visible, only the red msg "This conversation needs to be rekeyed"
• Click on "Rekey"
• See the same message box as before again.
• Go here and search & post about the issue.

log ID for edox is d745a5462b00ca3a1efbb71c
log ID for Toliop is bc66cae2732e1b861ba01a1c

Start with the reproduction sequence for devices “Toliop,” “edox,” and “Moto,” then inspect the attached behavior and the provided log IDs. Done means newly verified devices can open the private conversation without repeatedly showing “REKEY NEEDED” or requiring another paper key.