I was pretty much having the same problem, but managed to solve it (on 6 different devices - 4 iPads and 2 iPhones). My theory is that your iCloud backup is still there, but somehow following iOS9 the back is no longer associated with your iDevice. Hence why your backup shows as 0kb (but storage space in iCloud indicates the backup is still there). In addition, iOS9 has turned iCloud backup for all of your apps. Thus (depending on how much iCloud storage you have or the amount of data in your apps), you could run out of iCloud storage space.
The options really are to wait for Apple to fix the problem (but run the risk of not having any iCloud backups) or delete your old iCloud backup and start again. I opted to delete the old iCloud backup as I will be upgrading to a new iPhone 6s shortly and once my old iPhone 6 is gone, I don't think I will be able to delete backups associated with it (and hence will permanently lose iCloud storage).
The Solution (and yes it can sound like a bit of voodoo magic) I found was.
Backup Deletion Process
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 IMPORTANT. If you don't wait for iCloud to finish loading, your will not be able to delete your backup and you will get the "Cannot Delete Backup" error message.
3. Scroll down and click "Show all apps" and then click "Delete Backup". It should start to delete (but may take awhile). You should also see the amount of free iCloud space you have increase (once the backup has been deleted).
4. After Deleting the backup successfully, go back to the main iCloud settings page and turn on iCloud Backup (if not on already).
5. Go to the same Manage Storage page and select which items you want to backup to iCloud.
6. Go to iCloud Backup page and click "Back up Now" to perform a manual backup.
Now you have to wait for your backup to complete. Depending on the size of your backup, this could take awhile. If you just want to see if this works, do a small iCloud backup (by turning off iCloud backup on most of your apps). I did this initially and got the backup to complete in about an hour. With all of my things turned back on, it took 8 hours.
You may encounter the "Backup could not complete" error message. If you do, just select "Back up now" again. Whilst the backup did not complete properly, data has still been backed up and your backup should resume from where it left off.
Hope this helps and hopefully Apple will fix the problem shortly.
