Tout d'abord, on commence par enlever complètement grub.

aptitude purge grub-pc grub-common

puis on enleve ses fichiers de configuration pour éviter les mixs

rm -rf /etc/grub.d
rm -rf /boot/grub

Wala, maintenant, notre serveur est incapable de redémarrer. donc on ne reboot surtout pas avant d'avoir fini !
A présent, on installe grub

aptitude install grub

Et maintenant, il faut l'inscrire dans le MBR de votre disque dur. Pour ce faire, une simple commande suffit à le configurer par défaut, en prenant en compte les kernels actuellement installés.

grub-install hd0

ici on indique hd0, le 1er disque dur, sur lequel le MBR doit être écrit. Si votre config est un peu différente, voici comment faire pour indiquer le bon disque.

grub

find /boot/grub/stage1

lorsqu'on tape "find /boot/grub/stage1" cela permet à grub de nous indiquer sur quel disque et partition se trouve le fichier stage1, indispensable au démarrage.
Il m'a inidiqué hd0,0 pour 1er disque dur / première partition, met il peut vous indiquer par exemple hd1,3 pour 2è disque dur / 4è partition ;)
Enfin, on l'installe sur le MBR

root (hd0,0)
setup (hd0,0)

Enfin, et très important, il faut maintenant générer le fichier /boot/grub.menu.lst, qui n'existe pas encore. Pour ce faire, on tape la commande

update-grub

Et voilou, plus qu'à éditer votre bon vieux menu.lst suivant vos préférence de couleurs d'ordre etc... Merci la machine virtuelle :p