Eu tropecei nessa questão quando estava pesquisando o mesmo problema que surgiu do nada em minha AM2 EC2 de camada livre da Amazon que uso como servidor da Web.
Para ajudar a corrigir isso, iniciei este tópico: link
Como detalhado em minha solução (3o post no tópico), consegui trabalhar novamente:
$ sudo rm /var/lib/apt/lists/lock
$ sudo apt-get install -f
Espero que isso funcione para você também!