The Windows recovery console is crap. I've managed to save maybe 5% of the NTLDR issues I've had with it, and that's out of a lot of issues given how much I mess about with operating systems. It'll probably be less painless for you to download a Linux live CD like Knoppix or any other distro that provides a live CD, use that to back up your data to a USB drive or second hard drive and format/reinstall from there.

Have you added any partitions or hard drives lately? That's usually what buggers up my installations.