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".