Now, I can't tell you anything about iCloud and the backups (I don't use iCloud), but here's a suggestion for the backup error when you're connected to iTunes:
What I've seen when that error occurs is that somehow, the last backup that iTunes made on your computer has gotten corrupted. I, too, have gotten that notice and what I've done is to navigate to the backup folder on my computer and deleted it. Then, the backup process works fine again.
In case you don't have it handy, here are the addresses or locations of iTunes backups:
Mac: ~/Library/Application Support/MobileSync/Backup/
Windows XP: \Documents and Settings\(username)\Application Data\Apple Computer\MobileSync\Backup\
Windows Vista and Windows 7: \Users\(username)\AppData\Roaming\Apple Computer\MobileSync\Backup\
Of course, that's not all inclusive as there spare more systems out there. But, these should get you pointed in the right direction.
A note of caution/prevention: If you have more than one iDevice that you sync with that iTunes, just make sure you select the correct backup. Don't want to delete the wrong one...
Good luck and let us know how it goes.
Marilyn