Comment 1 for bug 300773

When you say removed these kernels did that involve removing the kernel-image and the linux-headers for each? The build link seems to come from the linux-headers package. So could you confirm which were removed and in which order.

I have just tried this here, removing the image first and then the headers:

apw@dm$ sudo dpkg -r linux-image-2.6.28-1-ub-generic
[...]
apw@dm$ sudo dpkg -r linux-headers-2.6.28-1-ub-generic
(Reading database ... 171800 files and directories currently installed.)
Removing linux-headers-2.6.28-1-ub-generic ...
dpkg - warning: while removing linux-headers-2.6.28-1-ub-generic, directory `/lib/modules/2.6.28-1-ub-generic' not empty so not removed.

In my case I have a bunch of module files:

apw@dm$ ls /lib/modules/2.6.28-1-ub-generic/
modules.alias modules.inputmap modules.pcimap modules.usbmap
modules.ccwmap modules.isapnpmap modules.seriomap
modules.ieee1394map modules.ofmap modules.symbols

It does appear that the kernel postrm script is not cleaning out all of the depmod generated files. That would not explain the files reported by Matt, as he does not have these files too I assume this kernel was never booted?