É claro que você não terá o pacote se não tiver o pacote em seu cache de listas. Normalmente, o método mais fácil é usar os meta-pacotes:
apt-cache depends linux-headers-generic
linux-headers-generic
Depends: linux-headers-3.8.0-31-generic
Conflicts: linux-headers-generic:i386
Ou, melhor ainda, para instalar cabeçalhos e imagens da mesma versão, use o linux generic
package:
apt-cache rdepends linux-headers-generic
linux-headers-generic
Reverse Depends:
linux-generic
apt-cache depends linux-generic
linux-generic
Depends: linux-image-generic
Depends: linux-headers-generic
Portanto, faça sudo apt-get update && sudo apt-get install linux-generic
e depois reinicialize o sistema para obter os cabeçalhos e imagens mais atualizados para o seu sistema.