Add me (actually my partner) to this list,
Iphone 5S 64GB running iOS 9.2.1, with 50GB iCloud account with 30GB free.
(iPad mini and iPhone 5C also attached to account, also fully up to date iOS 9.2.1).
This week I noticed her 5S had stopped backing up and also has stopped syncing iCloud photo library (the iPad and 5C had no problems and were synced perfectly). So I tried everything on the 5S, including deleting the backup from iCloud, erasing network settings, erasing all content and finally factory resetting via iTunes.
Nothing worked, still no backup to iCloud. After a factory reset the backup is ON in iCloud settings, but alway fails (the last backup could not be completed). It is not possible to deselect any app in the iCloud backup settings on the 5S. If I switch off iCloud backup, then I cannot switch it back on.
HOWEVER, if I use another iCloud account (in this case my iCloud account and not my partner's), the backup can be switched on and I can make a backup to iCloud. Switching back to my partner's iCloud account brings back the bug and the phone cannot be backed up.
My conclusion is that if in an iCloud account you delete a backup for a specific device (imei / serial number), it is not possible to make a new backup of this specific device. I suspect that somehow the device's backup is not completely deleted from the iCloud backup servers, and it therefore throws an error when a new backup is added/enabled, as there are still fragments of a backup for this device.
I have called Apple, explained all, managed to get quite far past the 1st line idiots that read out obvious scripts, but at manager level still ran into walls. Of course Apple denies the existence of this issue, and all people here are imagining this bug. The issue has been passed via a manager to iCloud specialists. So far no message back from them. So I'm stuck with a good as new 5S that won't backup.
If the iCloud backup servers are throwing Fatal 500 server errors, I hope somebody at Apple is looking at the icloud backup server logs, figuring out what's causing these fatal errors, and is racing against the clock to fix this in the next iOS update (9.2.2?) or even better, immediately on the iCloud side of this stupid fence.
Hope this sums it up,
Luke