I think I may have finally fixed this (though I don't really know the cause). If you have the issue, please try the following:
Download the latest ROM Manager off the Market: 220.127.116.11 currently.
Start the application.
Flash Legacy Recovery.
Choose 18.104.22.168. This is the recovery with the fix, it is a test recovery, so it isn't flashed by default.
Try a backup
Then test a restore of that backup!
Please let me know if this fixes the missing md5 problem. Been trying to track down this bug for a while!