initramfs fail after upgrade to 13.04, can't update system with apt-get / dpkg

The other night I received the prompt suggesting for me to upgrade from 12.10 to 13.04. I figured why not, and accepted the upgrade. I had very little interaction, just clicked the accept button, and came back to an upgraded machine in an hour or so.

initramfs now fails on old linux headers which I do not believe exist on my system, and I am unable to update anything on my system which depends on it (which is, pretty much everything, including graphics drivers, system updates, etc). I have been trying to resolve this issue for nearly a month now, and have learned quite a lot about Ubuntu/Linux in the process, though I am still not sure what I have to do to get past the following error.

Whenever I run commands such as:

sudo apt-get install  (with -f or not)
sudo apt-get upgrade
sudo apt-get dist-upgrade
sudo apt-get remove
sudo apt-get autoremove
sudo update-initramfs -u

I will receive the following messages/errors and will not be able to continue the process:

Setting up initramfs-tools (0.103ubuntu0.7) ...
update-initramfs: deferring update (trigger activated)
Processing triggers for initramfs-tools ...
update-initramfs: Generating /boot/initrd.img-3.8.0-31-generic
Fatal: open /boot/vmlinuz-3.5.0-21-generic: No such file or directory
run-parts: /etc/initramfs/post-update.d//runlilo exited with return code 1
dpkg: error processing initramfs-tools (--configure):
 subprocess installed post-installation script returned error exit status 1
Errors were encountered while processing:
 initramfs-tools
E: Sub-process /usr/bin/dpkg returned an error code (1)

Both sudo apt-get clean and sudo apt-get autoclean seem to have no effect. Using sudo apt-get update appears to run as expected, but no change as far as receiving the above error with subsequent commands.

Running sudo dpkg-reconfigure -a did not make a difference.

I've learned that there may be remnants of '3.5.0-21-generic' on my system. I've done my best at locating them and moving them to a tmp dir in my home. I've examined my /etc/apt/sources.list for any references to those headers, and there aren't any.

I've examined the contents of /var/lib/dpkg/info/linux-image-generic.list which is as follows:

/.
/usr
/usr/share
/usr/share/doc
/usr/share/doc/linux-image-generic
/usr/share/doc/linux-image-generic/copyright
/usr/share/doc/linux-image-generic/changelog.gz

I've checked the contents of all of those locations, and found no references to anything with 3.5.0-21, and in fact searching my entire system, the only files with that string in the name now exist in my new tmp dir that I moved everything into. I've also moved the references to linux-image-3.5.0-21-generic.* and linux-image-extra-3.5.0-22-generic.* that were in /var/lib/dpkg/info into my new tmp dir.

It seems to me that there isn't any place where vmlinuz-3.5.0-21-generic can be on my system. I can't find any when searching all files for anything containing 3.5.0-21. I still can't use initramfs, which implies that I can't update/upgrade my system, install new packages, or fix a few other issues that sprung up when I upgraded to 13.04.

What follows is (some of) my output from:

$ sudo update-initramfs -u -v
Available versions:  3.8.0-31-generic 3.5.0-41-generic
Keeping /boot/initrd.img-3.8.0-31-generic.dpkg-bak
update-initramfs: Generating /boot/initrd.img-3.8.0-31-generic
Adding module /lib/modules/3.8.0-31-generic/kernel/drivers/hid/hid.ko
... (mostly adding/calling happening here, hundreds of lines of output, seems successful)
Calling hook busybox
Adding binary /usr/lib/initramfs-tools/bin/busybox
Calling hook dmsetup
Adding binary /sbin/dmsetup
Adding library /lib/i386-linux-gnu/libdevmapper.so.1.02.1
rm -f ./etc/ld.so.conf.d/nvidia_settings.conf 
rm -f ./lib/firmware/cxgb4/t4fw.bin 
Building cpio /boot/initrd.img-3.8.0-31-generic.new initramfs
Fatal: open /boot/vmlinuz-3.5.0-21-generic: No such file or directory
run-parts: /etc/initramfs/post-update.d//runlilo exited with return code 1

Could anyone please help me understand this problem, and how I can alleviate it? What can I do to get past this? I really don't want to resort to completely reinstalling my system, is there any other way to fix this?