Eu tive esse problema agora. O que eu fiz foi limpar o pacote errante usando dpkg
no meu caso, depois atualizar e forçar a reinstalação:
sudo dpkg --purge linux-image-3.13.0-35-generic
sudo apt-get update
sudo apt-get -f install
O processo de instalação pode demorar um pouco, mas funcionou no final.