After 12 weeks since upgrading my 4S to 9.0x and further, having a popping message "This iPhone has not been backed up for x weeks" from time to time I have looked into this. Tried this and that from the comments to make sure iCloud backup works again (it works for my son with his 5S), nothing really worked 100% but - for me it seems that the backup is actually done. What I have tried:
1. Deleted the old backup. Before, total storage was 5GB, Available a little less. After they both were 5GB (which - if the numbers are correct - means the backup data was actually deleted).
2. Tried "Back Up Now" with all data except Photo Library. It was taking ~10 mins, showed the progress bar, calculated estimated time, and finished with no error message. If I look at the result at the bottom of the "Backup" screen it was still saying "The last backup could not be completed Last Backup: Never", and at "Manage Storage/Info" Latest Backup Never Backup Size 0 bytes.
But: when I look at the storage, it's Total 5GB, Available 4,2GB. Which means some 800MB (more or less what was my estimate adding together data volumes for 50+ apps) were used during the process, which looking at duration and no error message hints that some data has been written to iCloud.
Note: it also says in "Manage Storage/Info" Next Backup Size 107MB, and shows "Delete Backup" option at the bottom - which is not available right after you delete the backup).
So, the question for me now is - could this 800MB of data be useful when restored or not. If yes, it is less of a problem. I will spare some time for trying that in the (happy) New Year.