Hi :)
The easiest thing to try is to just get to a command-line and run
sudo update-grub
It sound like you have already tried more advanced methods. Can you run a LiveUSb session, or something, or transplant the hard-drive into a different machine (perhaps as an external drive)? If so then maybe chroot into the system and run the above command? Maybe completely uninstall grub to ensure you get all of the configuration files and everything and then reinstall?
It sounds like a config file has been corrupted a bit and a simple uninstall-reinstall tries to keep all the configs of things intact.
I really doubt that you'll need to reinstall the whole of debian to fix this! Hopefully someone with better understanding of Grub2 might help soon!