A maneira como consertei isso foi instalar manualmente uma nova versão do pacote linux-server
:
wget https://launchpad.net/ubuntu/+archive/primary/+files/linux-server_3.2.0.37.45_amd64.deb
sudo dpkg -i linux-server_3.2.0.37.45_amd64.deb
Se você estiver executando um sistema de 32 bits, precisará de um URL e um nome de pacote um pouco diferentes que você possa encontrar aqui .
Agradecimentos a @Eliah Kagan por sua resposta aqui link e ajuda com questões-meta-questões.