Did you install Ubuntu from a fresh installation or upgrade from 9.04? It
makes a difference because there are two versions of grub. Ubuntu 9.10 uses
grub2, but only if you install from scratch. If you upgrade it keeps legacy
grub.

To rewrite grub2 follow the instructions here in section 12:
http://ubuntuforums.org/showthread.php?t=1195275

To rewrite legacy grub follow instructions here:
https://help.ubuntu.com/community/GrubHowto
Look for the section called Backup, Repairing and Reinstalling GRUB. This is
one time where the commandline is easier so go with it.