Você precisa reinstalar o GRUB, você pode fazer isso de um chroot. Inicialize em um live CD, faça o chroot em seu sistema Linux e emita o grub-install .
Algo como o seguinte deve funcionar (assumindo que /dev/sda2 é / e /dev/sda1 é /boot e você deseja instalar no MBR em /dev/sda ):
mount /dev/sda2 /mnt
mount /dev/sda1 /mnt/boot
mount -t proc none /mnt/proc
mount -o bind /dev /mnt/dev
mount -o bind /sys /mnt/sys
chroot /mnt /bin/bash
grub-install /dev/sda
Ou se você estiver usando o LILO, use lilo /dev/sda .