La première chose à faire consiste à récupérer un LiveCD et booter dessus.
Dans un terminal, lancer la commande suivante :

$ sudo fdisk -l

Cette étape permet de savoir sur quelle partition se trouve votre distribution Linux. Pour mon exemple, j'utiliserais /dev/sda5 qui correspond à ma partition. Attention, il faut bien faire attention à monter les bonnes partitions au bon endroit.
Monter cette partition dans /mnt

$ sudo mount /dev/sda5 /mnt

si votre /boot est sur une autre partition, il faudra aussi la monter (/dev/sda6 sera utilisé dans l'exemple)

$ sudo mount /dev/sda6 /mnt/boot

Maintenant, monter le reste

$ sudo mount --bind /dev /mnt/dev

On va désormais se connecter en chroot sur le système ainsi préparé

$ sudo chroot /mnt 

Vous aurez peut-être à éditer le fichier /etc/default/grub pour qu'il corresponde à vos besoins

$ nano /etc/default/grub 

Lancer la commande update-grub pour créer le fichier de configuration

$ update-grub

Lancer la commande grub-install /dev/sda pour installer Grub2 sur le MBR

$ grub-install /dev/sda 

si vous rencontrez un problème, lancer la commande avec l'option --recheck

$ grub-install --recheck /dev/sda 

Tapez Ctrl+Dpour sortir de l'environnement chroot
une fois de retour sur l'environnement de base, démonter les disques, en premier /dev

$ sudo umount /mnt/dev 
$ sudo umount /mnt 

Redémarrez le système, et tout est rentré dans l'ordre.

Pour la petite histoire (qui reste à confirmer).. j'ai perdu mon Grub2 à chaque fois que je suis retourné sur mon Windows Vista