Eu precisava atualizar o kernel do meu sistema para a última versão disponível, então eu executei
sudo apt-get install linux-headers-3.16.0-37-generic
sudo apt-get remove linux-headers-3.13.0-37*
Então eu reiniciei.
Mas uname -r ainda mostra 3.13.0-37-generic
E não há como atualizar os kernels.
O que estou fazendo de errado?
Você não instalou o kernel, apenas cabeçalhos.
Se você quiser atualizar o kernel para o 3.16 no Ubuntu 14.04, a maneira correta é esta:
sudo apt-get install linux-generic-lts-utopic
O pacote meta extrairá os cabeçalhos e a imagem. Desta forma, os kernels serão atualizados através do processo de rotina.