Thank you for this thread, and the answers contained therein. My iPhone 5 was backing up to iCloud, but my iPad mini had stopped. It would try, and then fail pretty quickly. "iCloud backup could not be completed." And no amount of voodoo would get it working again. I was getting frustrated and almost ready to give up. (Restoring wasn't an option really as I am jailbroken on iOS 6.1.2 and now only iOS 6.1.3 is being signed.)
One related symptom I noticed was that when I would go to "Settings -> iCloud -> Manage Storage -> iPad mini" (in the hopes of toggling off Photo backup, at least temporarily,) the wheel would spin and it would never actually show the list of toggles. It would just sit on that screen forever. I knew that if I couldn't fix that, then the backup would never complete. And it never did... I tried lots and lots of things:
I deleted the old backup, toggling iCloud off and on again, both via iTunes as well as on the device itself (countless times)
I uninstalled PkgBackup (even though it was updated recently to fix this conflict)
I uninstalled a bunch of other non-essential Cydia tweaks
I deleted all of the photos on my iPad mini
I deleted my iCloud account and added it back (first as mac.com, then as icloud.com, then again as mac.com)
I ran iCleaner Pro and removed unused dependencies
I rebooted the iPad mini (countless times)
I sacrificed a black goat while chanting prayers in the name of Cupertino
...and nothing worked.
It was only when I reinstalled PkgBackup, in the hopes of following the tips in this thread, that I was FINALLY able to get it fixed. I didn't have to grant access to photos again, I didn't have to "activate" in settings. I merely reinstalled PkgBackup and ran a single backup there. And then went back to Settings -> iCloud and manually started a backup.
And it is currently performing that backup, with "about 16 minutes remaining."
Huzzah! Thanks for the push, gang. I feel a lot better knowing automatic wireless iCloud backups will be operational.