Você compila no Debian ou no Ubuntu (EDIT: depois de reler vejo que é meio implícito onde você diz "repositório do Ubuntu" acima) e então faz um pacote .deb
para ele? Você pode ter feito um pacote que não contenha os cabeçalhos.
O texto a seguir foi extraído de aqui :
If I think about it - it's possible that the kernel headers aren't installed because in the Debian kernel howto we create a kernel .deb package which doesn't contain the headers.
You can try to combine the Debian kernel howto with this one: http://www.howtoforge.com/kernel_compilation_ubuntu_p2
Run
fakeroot make-kpkg --initrd --append-to-version=-custom kernel_image kernel_headers
instead of
fakeroot make deb-pkg
This should create a kernel headers deb package.
If that doesn't work, you can still compile a kernel the traditional way, without creating a deb package, as shown here: http://www.howtoforge.com/kernel_compilation_fedora_p2 That way the headers will be installed for sure.