Comment 17 for bug 454220

This is still an issue.
Since the default kernel was automatically changed to a -pae variant some time this year, every time the kernel is updated the matching -pae header is not updated along with it even though the installed proprietary nvidia driver's kernel module depends on it.
After the next reboot the X server fails to start (which was a major nuisance for me at the beginning since the text mode couldn't be displayed on the attached TV and I had to attach a monitor for debugging) failing to load nvidia.ko.
So now I have to check after every update whether the kernel image was updated and in this case to manually install the matching -pae header package, otherwise I would get a black screen after reboot again (at least now I have a textmode my TV can handle...).

Today the kernel image was updated from 3.0.0-12-generic-pae to 3.0.0-13-generic-pae, linux-headers-3.0.0-13-generic-pae was again not installed automatically. After installing it manually run-parts automatically created
/lib/modules/3.0.0-13-generic-pae/kernel/drivers/video/nvidia
/lib/modules/3.0.0-13-generic-pae/kernel/drivers/video/nvidia/nvidiafb.ko
/lib/modules/3.0.0-13-generic-pae/updates/dkms/nvidia_current_updates.ko
/lib/modules/3.0.0-13-generic-pae/updates/dkms/nvidia_current.ko
/lib/modules/3.0.0-13-generic-pae/updates/dkms/nvidia_173.ko

So yes, this is still a VERY annoying issue until today in Oneiric.
There should be a dependency making sure that the matching kernel header is installed after an update of the kernel image if the nvidia X-server is installed.