Join the club mate, me and my wife haven't been able to do a iCloud backup for 2 months now, we get the exact same message. googled like mad, tried everything I found and I even restored the phone as a new phone but that didn't work either.
Misses got a brand new 6S a couple of weeks ago, still doesn't work on that, very annoying that nobody knows how to fix it and Apple aren't addressing it, unless the upcoming iOS 9.1 sorts it, but I won't hold my breath!
We've been backing up on iTunes using the computer, it's actually faster than doing an iCloud backup I've found, just the hassle of turning the pc on and getting a usb cable. Oh and make sure you have win7 or above otherwise you can't backup on iTunes either!!