Isto é muito semelhante ao Ubuntu 13.10, kernel ainda 3.8.0-31-genérico --- respondendo aqui para que esta seja uma pergunta / resposta mais genérica.
Em algum momento do processo de atualização, os meta-pacotes do kernel são "perdidos". A solução básica é reinstalar o pacote do kernel genérico:
sudo apt-get install linux-generic
que deve fornecer os pacotes e cabeçalhos corretos do kernel depois de um:
sudo apt-get update; sudo apt-get upgrade
( obviamente se você tem -rt ou -lowlatency ou outros kernels "com sabor" você tem que adaptar isso ao seu caso)
Em algum momento, o sistema está (erroneamente) convencido de que possui o kernel mais novo: nesse caso, tente
sudo apt-get install --reinstall linux-generic