Roubado de http://ubuntuforums.org/showthread.php?t=947124 . Eu segui estas instruções deste mesmo post há algum tempo atrás. Demorei um pouco para encontrá-lo novamente.
sudo apt-get update para atualizar sua lista de atualizações disponíveis.
sudo apt-get autoclean para remover pacotes parcialmente instalados.
sudo apt-get clean para clamar o cache do apt.
sudo apt-get autoremove para remover dependências desnecessárias.
sudo dpkg --remove -force --force-remove-reinstreq broken-pakage removerá qualquer pacote corrompido que você encontrar nas mensagens de erro.