Sometimes (only happened to me once) you'll get this error on bootup. Most people get it when they dual-boot Vista with Ubuntu (or any other Linux distro). I got this before I even could access the Grub menu (The black screen where you choose which OS to boot). So I loaded Ubuntu 8.10 LiveCD and opened Terminal and typed:

mkdir /mnt/root
mount /dev/xxx? /mnt/root
chroot /mnt/root /bin/bash
grub-install /dev/xxx


Or simply just this:

chroot /mnt/root
grub-install /dev/xxx