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.
This worked for me - sadly, only once!
I got what appeared to be a good backup. Then tried one more time. Got the dreaded "last backup could not complete" again. Tried again, same thing. So, not knowing what to do, deleted the backup. Started backup again, got "last backup could not complete". Uh, oh...
I'm relating my experience here in the hopes that it may help someone out.
As an experiment, I turned iCloud Backup off, then on again.
I set ALL Apps OFF for Backup. Then I did an iCloud Backup. Hmn, that appeared to create a backup.
All of the Apps were showing "no data". I just set the first app, MPod in my case, to on for backup and did an iCloud Backup. That worked.
Also, "no data" was starting to change to show data size for some of the apps.
I started, one by one, to set random but frequently-used apps to on for backup, then doing an iCloud Backup - one app at a time. That seemed to be working. When I set Pandora on for backup and tried the iCloud Backup, I got "last backup could not complete". Ah, ha!
I deleted the Pandora App and re-downloaded it. Set it on for iCloud Backup and it worked!
I next set about five random apps to on for the Backup. That worked too. Finally, I set all of them on and got a successful backup.
I'm not sure if this is coincidence, or if Pandora was somehow causing the backup to fail. But iCloud Backups are giving the appearance of working now.