O pacote do kernel já está instalado - você o danificou. Reinstale-o.
sudo apt install --reinstall linux-image-4.4.0-59-generic linux-image-extra-4.4.0-59-generic.
Observe a diferença nos nomes:
Os pacotes 'linux-image' e 'linux-image-extra' são as imagens reais do kernel.
O pacote 'linux-image-generic' é meramente um meta-pacote que se refere aos pacotes atuais de imagens do kernel ... então as atualizações funcionam.