I was having the same problem: With iOS 9.0.x any attempt to back up the device to iCloud would result in the error:
The last backup could not be completed
I tried the numerous suggestions, turning off backups, logging out of iCloud, rebooting, upgrading, etc. and nothing would work.
Finally, the solution came after I installed an app called "iOS Console" which enabled me to look at my iOS [iPhone] device logs while backing up the device. This led me to the following error (cryptic, but I'm an I.T. guy and I was able to decipher it):
Oct 6 16:13:41 Stinson backupd[242] <Warning>: WARNING: Handling save error for record <CKRecordID: 0x125f5b310; F:A3998E3A-5816-4267-B3C8-427C892942DB:N+ou0zGt//g+H727vBruGFj9dng=:101438000:+ 7Kk:(_defaultZone:__defaultOwner__)>: <CKError 0x127031c10: "Asset File Modified" (17/3003); "Saving asset failed">
Oct 6 16:13:41 Stinson backupd[242] <Warning>: ERROR: Failing save of record <CKRecordID: 0x125f5b310; F:A3998E3A-5816-4267-B3C8-427C892942DB:N+ou0zGt//g+H727vBruGFj9dng=:101438000:+ 7Kk:(_defaultZone:__defaultOwner__)> after 1 attempts with error <CKError 0x127031c10: "Asset File Modified" (17/3003); "Saving asset failed">
Oct 6 16:13:41 Stinson backupd[242] <Warning>: ERROR: Failed to upload AppDomainGroup-group.com.facebook.Facebook:4EE2D977-A0FA-483C-B5BC-4986618FBE38 .dmp (<CKError 0x127031c10: "Asset File Modified" (17/3003); "Saving asset failed">)
You'll notice the path "AppDomainGrou-group.com.facebook.Facebook:…" in the error. It appear as though a corrupted (or otherwise unreadable) Facebook preference file or bundle was preventing the backup.
I simply deleted the Facebook app, and was able to backup my device after doing so.
I hope this helps you solve your iOS 9 backup issues. Note, it may not be Facebook that's causing the problem. You may have to look at your own device logs to determine which app is causing the problem.
-David