Ça serait pas plutôt linux-image-… et linux-headers-… ? 
$ aptitude search kernel-image kernel-headers -F '%p'
linux-kernel-headers [note: c'est un paquet virtuel]
$ aptitude search linux-image linux-headers -F '%p'
linux-headers
linux-headers-2.6
linux-headers-2.6-amd64
linux-headers-2.6-openvz-amd64
linux-headers-2.6-vserver-amd64
linux-headers-2.6-xen-amd64
linux-headers-2.6.32-5-all
linux-headers-2.6.32-5-all-amd64
linux-headers-2.6.32-5-amd64
linux-headers-2.6.32-5-common
linux-headers-2.6.32-5-common-openvz
linux-headers-2.6.32-5-common-vserver
linux-headers-2.6.32-5-common-xen
linux-headers-2.6.32-5-openvz-amd64
linux-headers-2.6.32-5-vserver-amd64
linux-headers-2.6.32-5-xen-amd64
linux-headers-3.1.0-1-all
linux-headers-3.1.0-1-all-amd64
linux-headers-3.1.0-1-amd64
linux-headers-3.1.0-1-common
linux-headers-3.2.0-rc4-all
linux-headers-3.2.0-rc4-all-amd64
linux-headers-3.2.0-rc4-amd64
linux-headers-3.2.0-rc4-common
linux-headers-3.2.0-rc4-common-rt
linux-headers-3.2.0-rc4-rt-amd64
linux-headers-amd64
linux-headers-misdn
linux-image
linux-image-2.6
linux-image-2.6-amd64
linux-image-2.6-openvz-amd64
linux-image-2.6-vserver-amd64
linux-image-2.6-xen-amd64
linux-image-2.6.32-5-amd64
linux-image-2.6.32-5-amd64-dbg
linux-image-2.6.32-5-openvz-amd64
linux-image-2.6.32-5-openvz-amd64-dbg
linux-image-2.6.32-5-vserver-amd64
linux-image-2.6.32-5-vserver-amd64-dbg
linux-image-2.6.32-5-xen-amd64
linux-image-2.6.32-5-xen-amd64-dbg
linux-image-3.1.0-1-amd64
linux-image-3.1.0-1-amd64-dbg
linux-image-3.2.0-rc4-amd64
linux-image-3.2.0-rc4-amd64-dbg
linux-image-3.2.0-rc4-rt-amd64
linux-image-3.2.0-rc4-rt-amd64-dbg
linux-image-amd64
linux-image-openvz-amd64
linux-image-vserver-amd64
linux-image-xen-amd64
Edit : ah oui mais si warnings édite son message en même temps que je poste, aussi… 