I've had this problem as well and here's how I fixed it:
1. Connect your iPhone to iTunes and create a backup to your Mac/PC. Make sure that you make a backup of all the items you've selected for backup in your iCloud settings.
2. Once you've succesfully created a backup using iTunes, disconnect your phone.
3. Go in iCloud settings on your phone and delete your backup. This may take a while before it's finished.
4. Now create a new backup using iCloud. If this fails again you probably have a different issue than I had. But at least you've got a backup on your Mac/PC.
By "Go in iCloud settings on your phone and delete your backup," do you mean just go to Settings > iCloud > Storage & Backup > Manage Storage and swipe the iPhone to get it to delete?
Unfortunately I tried that, along with your other steps, but had no luck. The progress bar went as far as about 75 percent of the way across, but when I checked back, it again said the Last Backup was Never.
I did a bit of digging on the Apple support site and the only thing I could find was: make sure that there's at least 50MB of free space on your iOS device.
Could that be the case?
Other than that, I guess this would put me at my wits end. I'd either call in for support. Particularly since you've bought extra iCloud space.
Thanks for checking Harry, much appreciated. I've got about 40 GB of free space on my iPhone, so that's not it. I've been experiencing a bunch of iOS and iCloud problems recently in addition to this one (iTunes Match not working post iOS 6 upgrade, most reminders not appearing on the iCloud website), so it's possible this issue is connected.
Guess how I fixed it. I deleted my icloud account, and just synch using itunes again. I have repeatably reset my ipod touch, and computer, but to no avail. I have tried every suggestion, I've read in these forums. Either there is a problem syncing my mail or contacts over the cloud, or if I then try through itunes, cause it won't sync through the cloud, I will get a continous message saying waiting for changes to be applied in step 5. The main reason I got an imac, was for calendar & contact syncing, through my PDA. This Cloud idea, has potential, but not how it (doesn't work) now. Yes I realize there is probably something, that I have to change in either my computer, or ipd touch settings, but until you make this change more obvious, himans are not going to figure it out. Like say (when you first try too connect your icloud account, it says step 1., step 2. ... Instead I'm getting messages like remove mail account from ipod (can't be done, unless you remove your entire icloud account), or an endless 'waiting for changes to be applied.' This user will not be upgrading to Maverick, or the cloud, until you make it a lot more user friendly. Also if you ever make them both mandatory for using an apple, I will automatically switch to a PC, unless you somehow make the service more user friendly. I am a long time apple user, going back to the mid 80's, but won't think twice about a change, Cap'n Cook.