iCloud syncing problem

I have upgraded my iPhone 4 to version 5.0, my iTunes to 10.5, set up a fully functional iCloud account, and set my backups to iCloud on both my iPhone and iTunes.

However... when I go into Settings -> iCloud -> Storage & Backup on my iPhone and click "Back Up Now", I only get the status bar which says "Backing Up", and "Estimated Time Remaining...". It's never progressed past this point. It stays there for some time until is reads "There was a problem completing the backup. Please try agin later. Last Backup: Never"

When I check my iCloud in System Preferences on my MacBook Pro (v. 10.7.2), it tells me that I have an incomplete backup in the cloud, but I don't know when it got there.

Any guidance toward how to get iCloud backups working? Thanks!