Como você descobriu, remover arquivos antes de eliminar o pacote causa problemas para o gerenciador de pacotes. Você basicamente tem que restaurar as coisas que você apagou, que o gerenciador de pacotes está reclamando. Os arquivos restaurados podem ter tamanho zero, o gerenciador de pacotes não se importa, então use o comando "touch". por exemplo:
sudo touch /boot/vmlinuz-4.4.0-70-generic
Você pode ter que criar alguns diretórios também, mas quando o gerenciador de pacotes encontrar os arquivos desejados, ele será concluído com êxito.