Not much help, I'm afraid, but I spent about a day trying to solve this error during a hardware upgrade and complete disk restore from a recent backup. I tried various things using Knoppix etc. but no go. I ended up doing a clean installation, restoring a desktop backup, and upgrading as needed. (Of course, I still had my production server running until the new machine was ready to take over).
Good luck, I hope you have a recent backup of your important data.
/Jens