O gerenciador de pacotes está reclamando sobre a impossibilidade de excluir um arquivo ausente. Então, dê o que quiser! Eu encontrei mesmo um arquivo de comprimento zero vai fazer. Em / boot, recrie os arquivos ausentes:
sudo touch vmlinuz-3.8.0-25-generic
etc. Em seguida, basta executar a limpeza em todos os pacotes associados:
sudo apt-get purge 'apt-cache pkgnames | fgrep 3.8.0-25'
(Você será solicitado a confirmar a remoção).