Acabei de remover todos os arquivos com o comando abaixo.
sudo apt-get remove linux-headers-3.19.* linux-image-3.19.* && sudo update-grub
Voltei para 3.18.-alguma coisa. Eu então corri os mesmos passos e parece ter funcionado o segundo passo.
Não sei por que esse erro ocorreu, mas a remoção dos arquivos e o reinício ajudaram.