Se você estiver usando o grub2, basta executar um sudo update-grub
para encontrar os sistemas operacionais corretos e gerar um novo cfg.
De um CD ao vivo, você terá que montar sua partição:
sudo mkdir /mnt/root
sudo mount -t ext3 <your ubuntu partition, example /dev/sda4> /mnt/root
sudo mount -t proc none /mnt/root/proc
sudo mount -o bind /dev /mnt/root/dev
sudo chroot /mnt/root /bin/bash
sudo update-grub