I have encountered a problem like this all i have done is reinstalling the grub loader in mandriva.
-It should be the same kind of problem and the same solution on all distros, just try my way, it's not harmful as long as you do not clik "format the hard disk".
With Mandrake or Mandriva, and probably with Ubuntu, you boot on the first install CD (or on the install DVD), choose "install or update", then choose "update", it verifies a lot of things and you see "installing the bootloader". Choose to put the boot loader on your first disk, and everything should go fine.
Hope this helped.