i do have the same problem.

I upfraded from hardy to intrepid RC and notice that menu.lst is not updated
with new kernel from RC.

Dumb me... I used the system cleaner which purge old kernels and boom... i can't
boot anymore

It's more than just the kernel that gets changed -- there's the C lib
and header files (for those doing development and/or compiling).

Take a look at the /boot directory on your system; here's wgat's on
mine this instant (minus the leftmost columns which Yahoo would mangle):

total 53868
422667 2008-05-28 19:39 abi-2.6.24-18-generic
422667 2008-08-20 21:46 abi-2.6.24-19-generic
422838 2008-10-21 20:12 abi-2.6.24-21-generic
80071 2008-05-28 19:39 config-2.6.24-18-generic
80049 2008-08-20 21:46 config-2.6.24-19-generic
80062 2008-10-21 20:12 config-2.6.24-21-generic
4096 2008-10-27 18:58 grub
7455526 2008-06-03 23:20 initrd.img-2.6.24-18-generic
7455545 2008-06-03 23:20 initrd.img-2.6.24-18-generic.bak
7494286 2008-08-26 19:06 initrd.img-2.6.24-19-generic
7494932 2008-08-13 02:05 initrd.img-2.6.24-19-generic.bak
7496651 2008-10-27 18:17 initrd.img-2.6.24-21-generic
7496804 2008-10-14 20:29 initrd.img-2.6.24-21-generic.bak
103204 2007-09-28 03:06 memtest86+.bin
905012 2008-05-28 19:39 System.map-2.6.24-18-generic
905170 2008-08-20 21:46 System.map-2.6.24-19-generic
905617 2008-10-21 20:12 System.map-2.6.24-21-generic
1921528 2008-05-28 19:39 vmlinuz-2.6.24-18-generic
1921464 2008-08-20 21:46 vmlinuz-2.6.24-19-generic
1920760 2008-10-21 20:12 vmlinuz-2.6.24-21-generic

and here's the tail end of my /boot/grub/menu.lst:

## ## End Default Options ##

title Ubuntu 8.04.1, kernel 2.6.24-21-generic, 21-OCTOBER-2008
root (hd0,0)
kernel /boot/vmlinuz-2.6.24-21-generic
root=UUID=4b9e32d4-0db9-402c-be33-e9c35be3a81b ro quiet splash
initrd /boot/initrd.img-2.6.24-21-generic
quiet

title Ubuntu 8.04.1, kernel 2.6.24-21-generic (recovery mode)
root (hd0,0)
kernel /boot/vmlinuz-2.6.24-21-generic
root=UUID=4b9e32d4-0db9-402c-be33-e9c35be3a81b ro single
initrd /boot/initrd.img-2.6.24-21-generic

title Ubuntu 8.04.1, kernel 2.6.24-19-generic, 20-AUGUST-2008
root (hd0,0)
kernel /boot/vmlinuz-2.6.24-19-generic
root=UUID=4b9e32d4-0db9-402c-be33-e9c35be3a81b ro quiet splash
initrd /boot/initrd.img-2.6.24-19-generic
quiet

title Ubuntu 8.04.1, kernel 2.6.24-19-generic (recovery mode)
root (hd0,0)
kernel /boot/vmlinuz-2.6.24-19-generic
root=UUID=4b9e32d4-0db9-402c-be33-e9c35be3a81b ro single
initrd /boot/initrd.img-2.6.24-19-generic

title Ubuntu 8.04.1, kernel 2.6.24-18-generic, 3-JUNE-2008
root (hd0,0)
kernel /boot/vmlinuz-2.6.24-18-generic
root=UUID=4b9e32d4-0db9-402c-be33-e9c35be3a81b ro quiet splash
initrd /boot/initrd.img-2.6.24-18-generic
quiet

title Ubuntu 8.04.1, kernel 2.6.24-18-generic (recovery mode)
root (hd0,0)
kernel /boot/vmlinuz-2.6.24-18-generic
root=UUID=4b9e32d4-0db9-402c-be33-e9c35be3a81b ro single
initrd /boot/initrd.img-2.6.24-18-generic

title Ubuntu 8.04.1, memtest86+
root (hd0,0)
kernel /boot/memtest86+.bin
quiet

title REBOOT
reboot
### END DEBIAN AUTOMAGIC KERNELS LIST

I'm sorry I cannot help you directly; perhaps the /boot and menu.lst
from my system I just posted may assist you manually entering the
data into /boot/grub/menu.lst

Just checked Synaptic and there's nothing in Preferences or Repositories
that seems like it would prevent updating of /boot/grub/menu.lst

My system seems to be running fine, but this (not updating menu.lst)
is clearly a new problem.

Although this is after-the-fact, it's best to leave several prior
kernels around "just in case".

Even weirder is that both the August 25 and October 21 kernel updates
are both 2.6.24-21-generic. The "October 21" is what I just received
within the past hour. Strange.

You can rewrite grub using your live CD. No need to re-install.
www.howtogeek.com/.../reinstall-ubuntu-grub-bootloader-after-win\
dows-wipes-it-out/

I did an upgrade from beta to RC and it gave me an option to use a new grub or
keep the old. I kept the old as it is modified.