Abaixo está uma maneira aparentemente radical de possivelmente resolver esse erro.
Eu vi isso nos fóruns do Ubuntu e uma referência a: link
Eu tentei isso no meu sistema (server11) e não funcionou, mas estou colocando a solução aqui de qualquer maneira. No meu sistema, eu já podia ver em apt-get clean ele já deu o mesmo erro de antes.
sudo mv /var/lib/dpkg/status /var/lib/dpkg/status-bad
sudo cp /var/lib/dpkg/status-old /var/lib/dpkg/status
sudo mv /var/lib/dpkg/available /var/lib/dpkg/available-bad
sudo cp /var/lib/dpkg/available-old /var/lib/dpkg/available
sudo rm -rf /var/lib/dpkg/updates/*
sudo rm -rf /var/lib/apt/lists/*
sudo mkdir /var/lib/apt/lists/partial
sudo rm /var/cache/apt/*.bin
sudo apt-get clean
sudo apt-get autoremove
sudo apt-get update
sudo dpkg --configure -a
sudo apt-get install -f
Referência original: link