I had a similar problem.
I had a bual-boot with Windows7 and Ubuntu installed on my computer, and wanted to replace ubuntu by Fedora15.
Fedora have an installation option that permit to replace all Linux installation on the computer, so I tried it.
Fedora has been well installed, but that's when I wanted to start with Windows that the problem appeared. When I selected 'Other' in the Grub menu, I got :
"MBR is missing, press Ctrl+Alt+Del to restart"
In fact, the problem came from the Grub configuration.
In /boot/grub/grub.conf, the 'other' configuration was :
that I changed by :
rootnoverify(hd0, 0) #you must change the partition number
And then Grub was able to launch the boot on the right partition.
Hope that it will help you...
PS: sorry, I'm french, and so my english may not be good. Take a look on this link about Grub, it's quite interesting (but in french): Grub - Lea Linux