(8 hours later...) Yep, that worked: I did an erase-then-copy, and the backup is now fully bootable.
I wonder what caused the problem though. Have you tried Smart Updating a Mountain Lion backup to Mavericks yourself? Are there any reports of that working? I wonder if the problem was specific to me.
It seems that Mac OS X does have a "FIPS mode" that performs some kind of cryptographic checks on startup:
http://support.apple.com/kb/ht5239
From the error message I got, it sounds like this could have gotten enabled or at least be related in some way. I have no idea why/how though.