Inicialize o Linux usando o CD de instalação do Ubuntu (ou USB), abra um terminal e faça:
sudo mount /dev/sda? /mnt (replace sda? with the partition where you installed the root fs, use gparted if you don't know)
sudo chroot /mnt
#if you have a separate boot partition: mount /boot
mount /dev
mount /proc
mount /sys
update-grub
grub-install /dev/sda
Se não houver erro, você pode reiniciar e deve funcionar.