I'm amazed of the length of this discussion, and the complexity of all the solutions presented. Here is a good one:
1. Get a Debian netinst installer on http://www.debian.org/devel/debian-installer/
2. Boot it and choose the special entry for recovering
3. When it offers you various choices, choose to install again Grub (there is a special entry for this)
That's all! If you already did point 1, the rest should need less than one minute.