Boot into the Ubuntu Live CD and run a few commands.

First, identify which is the Ubuntu partition:

sudo fdisk -l

Next, mount it (replacing sda2 with the appropriate partition number):

sudo mount /dev/sda2 /mnt

And finally, reinstall Grub (replacing sda with the appropriate hard drive):

sudo grub-install --root-directory=/mnt /dev/sda

Now, run this:

sudo update-grub

This should detect your Ubuntu installation and add it to the Grub menu.