Tonight I ran into a weird upgrade issue on a Ubuntu 12.04-LTS server. The original cause of this issue is that the server had been running long enough to fill up it's /boot partition with old kernel files. So at some point an upgrade failed due to the full drive. So tonight when I tried to do an upgrade, which happened to include a new kernel, I got a report of a previous failure and that I should run "apt-get -f install" to fix the it.
That's when the problems started. As you can see from the output below, this failed as well. For those who just want the answer, jump to the TL;DR section.