I did 5 backup/restores last night while testing out the new auto-backup features I'm working on. I had 2 bad md5sum errors related to the sd-ext partition, none on the others. The logs haven't been much help trouble shooting. So I've added a check after the md5sums are generated, to test them against the files. If they don't match, an error will be reported, auto-backup will stop, and the default recovery menu will appear, along with a message telling you what happened, and recommending you re-do the backup manually.
Note- I have made zero changes to the backup code when accessed from the menus, it's pure ClockworkMod.
Sorry for the troubles, but thank you for reporting them!
+1 for LeslieAnn's suggestion for handling backups. I'm a bit less OCD about it. I use TitaniumBackup to backup any recently updated/installed apps, and use ADW's backup/restore feature. I make a backup in recovery once every two weeks to a month. If there are ever any issues, I have a known good backup, and TitaniumBackup's recently saved backups, so there's always a means to recover all apps. Using LeslieAnn's suggestion, you will also have backups of everything else on your phone, such as sms/mms, bookmarks, app settings, etc.