I always thought that they only managed the public keys.
I thought that your backup is stored in iCloud or Google Drive unencrypted. Facebook doesn't have direct access to that. You phone must be already logged in to those services.
Some folks will tell me "but it's end-to-end!" and it feels kinda like they're telling me that it's "what plants crave."
EDIT: if you don't believe me, turn on the setting, have a friend reinstall the app and watch the re-keying happen. It's indistinguishable from an attack unless you trust the broker. If you trust the broker, then why claim it's "end to end"? Also refer to the various articles that describe this behavior that WhatsApp says is by design.
Double EDIT: why is it this way by design? Because it would be a PITA if every time you replaced your lost phone your buddies got a warning that looked like "Either Dave has got a new phone or the NSA is attacking you. Resend ten years of hilarious memes and intimate conversations to whoever is on the other end?" Real cryptography comes with real inconveniences when you lose your keys. It's the same kind of headache with securing cryptocoins - if you lose the secrets you lose the money. Trusting an agent is the only way to escape, but it comes at a significant cost. Cryptocoin custodians like exchanges get attacked all the time. And communication broker/relays get lawful intercepts all the time.
AFAIK, it won't resend already received messages; if the other end didn't have a backup, these ten years of old messages are lost for that end. I don't know whether it will resend sent but not yet received messages, and it certainly will use the new key for new messages (but at that point, you already received the "key changed" alert).