If the Ultimate boot CD doesn't work, try Hiran's Boot CD http://www.hirensbootcd.net. It has a lot of hard disk diagnostics tools.

How old is the drive? With the prices today, you might want to buy a new one anyway and clone the drive. If fixmbr from the recovery console doesn't work, try chkdsk /f /r from the recovery console.

"When in doubt, rip it out". If the drive is flaky, it will only get worse. You can replace it now or lose your data later.