Comment 202 for bug 642421

Verified with 2.6.35.28.

NOTE: Due to the workarounds supplied above, I was no longer getting automatic kernel updates. Apparently, when the above workaround failed, and I reverted the manual installation of that kernel, I accidentally removed the wrapper packages to get the latest kernel (linux-image-generic linux-headers-generic)

{{{
callaghan@family:~$ dpkg -l 'linux-image*'

||/ Name Version Description
+++-========================-========================-================================================================
un linux-image <none> (no description available)
un linux-image-2.6 <none> (no description available)
ii linux-image-2.6.35-22-ge 2.6.35-22.35 Linux kernel image for version 2.6.35 on x86/x86_64
rc linux-image-2.6.35-25-ge 2.6.35-25.44 Linux kernel image for version 2.6.35 on x86/x86_64
un linux-image-generic 2.6.35.28.36 Generic Linux kernel image
}}}

{{{
callaghan@family:~$ dpkg --list linux-headers-*
Desired=Unknown/Install/Remove/Purge/Hold
| Status=Not/Inst/Conf-files/Unpacked/halF-conf/Half-inst/trig-aWait/Trig-pend
|/ Err?=(none)/Reinst-required (Status,Err: uppercase=bad)
||/ Name Version Description
+++-=================================-=================================-==================================================================================
un linux-headers-2.6 <none> (no description available)
un linux-headers-2.6-686 <none> (no description available)
un linux-headers-2.6-amd64 <none> (no description available)
ii linux-headers-2.6.35-22 2.6.35-22.35 Header files related to Linux kernel version 2.6.35
ii linux-headers-2.6.35-22-generic 2.6.35-22.35 Linux kernel headers for version 2.6.35 on x86/x86_64
un linux-headers-2.6.35-25 <none> (no description available)
un linux-headers-2.6.35-25-generic <none> (no description available)
un linux-headers-generic 2.6.35.28.36 Generic Linux kernel headers
}}}

In order to get automatic kernel updates again, I had to do:
{{{
sudo apt-get install linux-image-generic linux-headers-generic
}}}

Credit: trism on IRC (freenode, #ubuntu)