I'm having the same issues. Verification timed out. backup failed, try later. I want to just delete my iCloud account altogether, but it says that if I do, it will delete everything from my iPad. I have deleted all backups, and my iCloud is showing as having 5 Gb space, but I'm loathe to delete it, as I don't want to risk deleting envy thing, at the moment. My MacBook is broken, so I can't access iTunes from there, as my backup iBook, which I'm using temporarily, is only MacOSX10.4.
Any ideas anyone?