i had this problem, if you login to your one drive and go to settings->Options and then click on device backups on the left. You should see backups of all the Windows 8 and Windows Phone 8 devices you have. Delete the backup for your phone, give it a couple of minutes and then do the back up on the phone, it should go through this time.
Doing this worked for me, it's almost as if the backup saved is corrupt or incompatible with the backup the phone is trying to create.