Hey guys, I had the exact same problem. And I just registered to let you know how I got it solved.
First of all, what fischmanr said is correct. For some reason, after upgrading to iOS 9, photos are automatically set to On again, so if you don't have enough space make sure to turn them back off.
Here's what solved my problem:
1- Go to Settings-->iCloud-->Storage-->Manage Storage-->Select your device that you are having problems backing up.
2- Wait for the spinning wheel to finish (loading icon beside backup options). THIS IS VERY IMPORTANT (for some reason!).
3- Scroll down and click "Show all apps" (it's stupid, but trust me this is the only way I could do it)
4- Scroll all the way down, and click "Delete Backup" and then confirm deleting. If you got an error message saying that "the backup can't be deleted, try again later" that means you didn't wait enough. Let it finish loading.
5- After Deleting the backup successfully, go back to the main iCloud settings page, and go to Backup. If iCloud Backup is still On, turn it off then On again. If it was off already, just turn it on.
6- Go to the same page in step 1 again, and make sure that photos are off (if you want them off), otherwise just make sure that all the options are ok as you want them.
7- Go back to the Backup page and click "Back up Now".
It took me about 5 hours to get it done, but it now works fine.
Note #1: If after step 7 you got the same error message that it wasn't completed, just press "Back up Now" again, it should continue and finish. I got it to work from the second trial.
Note #2: If the whole thing failed, just keep repeating and cross your fingers
it will hopefully work! My friend had to do the whole thing 3 times...
Best of luck guys, and I hope I helped.