Your best bet to save time IMO is to boot a live cd. Save what you want to keep off of internal install to external drive or dvd media. Do a reinstall.
I say this because you said
I was removing out of date kernel headers and accidentally clicked mark for complete removal so I had to rebuild the kernel.
which does not make sense to me. I have completely removed kernel headers and kernel images and then ran
afterwards and never had a problem rebooting any of my linux installs (always being sure to keep 2 kernels for menu.lst). I don't run 12.04 though.
dpkg --list | grep linux-image
rc linux-image-2.6.32-21-generic 2.6.32-21.32 Linux kernel image for version 2.6.32 on x86
rc linux-image-2.6.32-24-generic 2.6.32-24.43 Linux kernel image for version 2.6.32 on x86
rc linux-image-2.6.32-25-generic 2.6.32-25.45 Linux kernel image for version 2.6.32 on x86
ii linux-image-2.6.35-22-generic-pae 2.6.35-22.34~lucid1 Linux kernel image for version 2.6.35 on x86