I updated to the latest Intrepid kernel, and when debconf asked if I wished to upgrade my menu.lst, I accidentally answered "Keep Current Version" instead of "Install Package Maintainer's Version", so the entry for the old kernel didn't appear in the boot list.
A sudo update-grub wouldn't fix it, though I found an open Launchpad Bug, in which it's suggested to rename your menu.lst, and update-grub again.
sudo mv /boot/grub/menu.lst /boot/grub/menu.old
and I'm back in business!
This does however mean I have to setup custom entries I had before, such as my no splash, my vga parameter, and the chainloader into the Windows partition.