Try the following:
Install SuperAntiSpyware Free Edition:
It has an option to restore the SafeBoot key that is deleted or corrupted by malware.
Download the program
Save to the Desktop
Double-click on the SUPERAntiSpyware setup file to launch the installer.
When done installing, open SuperAntiSpyware
Click on Preferences
Click: Repairs tab
Scroll down and select Repair broken SafeBoot key
Click Perform Repair and follow the prompts.
Let us know how it goes.
If no joy, did the computer come with its own restore CD or any other recovery method that you can try, if it offers a non-destructive repair/recovery option?