Comment 6 for bug 1305391

In my case, the /initrd.img and /vmlinuz symlinks were broken - pointing to nonexistent files. Correcting those symlinks by hand (and validating the grub.conf) allowed apt-get install -f to repair itself.

This is a bug, and I'm not sure about the root cause, but that was my fix.