Continuei pesquisando depois de postar o problema e encontrei uma resposta que me permitiu fazer a instalação e a atualização. Eu não tenho experiência suficiente para saber se a resposta que eu segui (abaixo) ou a solução postada por Zanna (obrigado!) É melhor.
A solução que usei foi publicada em este tópico onde Ox450 responde a sua própria pergunta, que é a seguinte:
A causa do problema:
Eu verifiquei o status do dpkg dos pacotes:
dpkg --status linux-image-3.13.0.57-generic
dpkg --status linux-image-extra-3.13.0-57-generic
A saída afirmou claramente que os pacotes estavam em mau estado. Eles não foram "totalmente instalados" como escrevi na pergunta acima.
A solução:
As entradas destes pacotes devem ser deletadas do arquivo de status do dpkg para que o apt-get funcione normalmente. Os passos são os seguintes:
Certifique-se de fazer um backup do arquivo de status se algo der errado.
sudo cp /var/lib/dpkg/status /var/lib/dpkg/status.backupOpen /var/lib/dpkg/status with your preferred text editor and search and delete ONLY the references of the broken packages. You must not delete anything else!
Execute o sudo apt-get upgrade para ter certeza de que tudo está resolvido.