[allending]

What's preventing Apple from reverting things on the backend to 'undo' the password change and allow the next authentication and backup attempt by the phone to work? Apart from unless the phone has been restarted in which case the FS is still encrypted so the backup wouldn't yet be possible until at least after the first unlock.

[themartorana]

Maybe they don't store previous passwords?

Edit: or are you suggesting iCloud be programmed to accept any password for this account?