When I received this error message, I found it had to do with the /boot partition being filled with many old kernel images and headers that were not removed after dist-upgrades. A temporary solution from this launchpad bug comment is quoted at the bottom of this post.
It's worth noting that Ubuntu is working on a fix through Apt, which as of 2013-03-26 is implemented in Precise, but pending on Quantal.
Warning: removing kernel packages can be dangerous, and might even
leave your system unable to boot, so please don't do this if you don't
understand what is going on.
I fixed this on my system by removing some old kernels, that I am not
using any more.
I checked what kernel I am using like this:
uname -r
This gave me a version number of a kernel I MUST NOT remove because I
am using it.
Then I checked what kernels were installed like this:
sudo apt-get remove linux-
I.e. I typed "sudo apt-get remove linux-" and pressed the TAB key
twice to see a list of possible completions. I chose the linux-image-*
and linux-image-extra-* packages that contained versions of the kernel
that I was not running, and removed them like this:
sudo apt-get remove linux-image-3.5.0-17-generic
linux-image-extra-3.5.0-17-generic linux-image-3.5.0-19-generic
linux-image-extra-3.5.0-19-generic
The exact list of packages in the "remove" line might be different for
you - I found it out by doing what I describe at the top.
Then I made sure the recently-downloaded kernel packages that failed
to configure were ok by running:
sudo apt-get upgrade
Warning: removing kernel packages can be dangerous, and might even
leave your system unable to boot, so please don't do this if you don't
understand what is going on.
