my 5C lasted backed itself up on the 1st October. Since then if I press the back up now button its starts estimating the time then after a short while it says the back up was not complete. any help would be great

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!!

You don't need the USB cable if you've set the phone up to sync over WiFi. It'll appear in iTunes when connected to the same network and can be backed up without the USB cable.

Looks like it's the iTunes route then . My iPad backs up fine automatically

Go into iCloud settings, Storage, Mangage Storage and then delete any backups you may have.
The backup should now be able to complete.
If that doesn't work then It could be possible that backing up both iPhone and iPad is causing the issue as there may not be enough iCloud storage available so another solution would be to purchase more. (79p a month for 50GB.)

What GONZO said.
After iOS9 I had loads of customers who's backup suddenly wouldn't complete (plenty of space too).
On every one deleting the existing backups from the cloud and starting again fixed it.
To be more specific though go to Settings/General/Storage (or Storage & iCloud storage)/ and then under the iCloud section tap Manage storage.
Tap on your iPhone backup and scroll down to delete it.
Then start a new backup.

Nope I've done that, deleted the 2.4GB backup that I had, now it says 0kb and 5.0GB of 5.0GB available on icloud, so there's 0 backups but it still says "backup was not completed".

Won't let me delete it, says cannot delete back up at this time

Yeah that's the original problem I had too, but for some reason it let me delete it this time.

I wouldn't worry about not being able to delete it anyway, it doesn't solve the issue, well not for me!

https://discussions.apple.com/thread/7220616

This worked for me if I didn't turn any of the individual app backups off