I don't think you need to reinstall.
Doesn't ubuntu include a live cd?
Boot that one (or in fact any other live linux cd), chroot to your
ubuntu root, mount boot and execute grub-install.
Of course first verify that it's not only a booting sequence gone
awry :)
In details:
1) Boot live cd.
2) Get to a console as root. In ubuntu:
Applications->Tools(?)->Terminal, sudo gnome-terminal.
3) Chroot to root:
i) mount your ubuntu root somewhere (let's assume /media/ubu)
ii) chroot /media/ubu
4) mount -a
5) grub-install /dev/sda1, where /dev/sda1 is your booter.
Good luck,
Klaus