Tente instalar um desses cabeçalhos com o kernel correspondente real:
$ sudo apt-get install linux-image-3.18.0-kali3-amd64
$ sudo apt-get install linux-headers-3.18.0-kali3-amd64
Agora, na inicialização, você deve ter os dois kernels listados. Experimente o novo. Se tudo estiver certo, desinstale o antigo ("kali 1 ") e compile o que quiser com os cabeçalhos. :)
PS: você tem certeza que executou todas as atualizações como root?