linux-image-generic-pae
é um pacote transicional, o que significa que ele não existe mais nos repositórios, pois linux-image-generic
inclui a funcionalidade pae.
Eu removo, certificando-se de que você tenha o pacote real instalado:
sudo apt-get install linux-image-generic
Se já estiver instalado, apenas no caso:
sudo apt-get install --reinstall linux-image-generic
E então:
sudo apt-get remove linux-image-generic-pae