De este bug da barra de lançamento , parece que a execução do seguinte corrige o problema:
sudo apt-get install aptitude libapt-pkg4.16
Se você obtiver unable to locate package libapt-pkg4.16
, execute:
apt-cache search libapt-pkg | grep 'package management' | cut -d ' ' -f1
E substitua libapt-pkg4.16
por qualquer resultado obtido (para mim em 14.04 é libapt-pkg4.12
)