All of the 9.0 betas and even GM would not backup my 6 Plus to iCloud, despite having 4+ GB free. It would always error out. After updating to the 9.1 beta it's been working. Though I have noticed every time I update to a new beta it turns the backup photos/camera roll option back on. I keep that off because it will instantly fill up iCloud since I have a 64GB device and go through thousands of photos a month. After turning that back off it'll work again.
It definitely seems related to iOS 9.0.x in my case. I'm sure it's working somewhere for others, but not for me, nor my 4s when it was on 9.0. But it's gone now so I can't report on that.