I have had a similar issue twice. When I upgraded from my iPhone 5 to a 6 and now again today when upgrading from my 6 to a 7. In both cases, when I first backed up my iPhone 5, I checked the encryption option and assigned a password saving it to my keychain. My keychain is backed up to iCloud. I backed it up going forward about every 45 days.
Two years later, when upgrading to an iPhone 6, I attempted to restore from my iPhone 5 backup. The password was filled in from my keychain, but not accepted. this was the first time I had attempted to restore my phone so I had never seen the saved password work. I opened keychain and verified the password saved was what I remembered. It was. I tried entering his password manually. It still didn't work.
Not finding a solution online, I gave up and started from scratch. This time, I again chose to encrypt the password but did not save it to my keychain. I saved it into 1Password instead. Now, two and half years later, I again go to restore from backup for my newly purchased iPhone 7. The dialog opened asking for my password. I verified it in 1Password. Entered it in. Failure!
