Hi there. I can't take full credit for this solution (someone mentioned it on the web), but it just worked for me, at least for a backup I just created(we'll have to see if the automated overnight backup succeeds tonight). I noticed that I was unable to delete my existing backup (from 8.4) from my phone. It kept saying try again. I can't say if this will work on a pc (although I presume it would using the windows icloud app), but I went on my mac, went to system preferences, then icloud. I then went to manage storage and, unlike on my phone, was able to delete the existing backup. Once I deleted it, I then went back to my phone and initiated a backup. It took awhile to backup, presumably because it was a full, not incremental backup, but it eventually succeeded. My theory is that ios 9 can't work with the existing 8.4 backup for whatever reason. So, starting from scratch with an ios 9 backup seems to work. If you're concerned about deleting your backup, just backup to itunes first. I tend to do that once a week anyway, since I don't totally trust icloud backup.
By the way, before posting this, I initiated a second backup. It took a minute or two (presumably, because it was incremental), and it also was a success. There may be a bug in how ios 9 does it's backup, but this may be a workaround. Also, my ipad was able to backup today, but I note that I was able to delete it's existing backup from the ipad, and that may be why it also succeeded.