Comment 3 for bug 220094

I also experienced this issue (in Lucid) with a kernel whose package had since been removed. I found by strace'ing update-initramfs that it gets the kernel list from the contents of /var/lib/initramfs-tools/. There's one entry there per kernel. Deleting the one for my removed kernel fixed the problem.