Eu tive o mesmo problema, mas com libnss3, libnss3-nssdb e libnss3-1d. Eu tinha instalado alguns pacotes na família libnss3, mas não todos, e eles parecem ser interdependentes uns dos outros. Em outras palavras, eu tinha alguma incompatibilidade de versão e estava preso.
apt não pôde fazer nada por causa de dependências não satisfeitas, então os guias sugerindo ppa-purge, ou fazendo downgrade de apt-cache usando o Synaptic (que eu não tenho instalado) não ajudaram muito. Algumas das soluções que encontrei significariam que cerca de 100 pacotes, incluindo tudo relacionado a Java, cada navegador, quase tudo relacionado a GUI, seria removido.
Aqui está o que eu fiz no final. Pode quebrar ainda mais o seu sistema, por isso, proceda com cautela e por sua conta e risco!
Eu encontrei os pacotes corretos (a versão que eu tinha instalado antes do desastre) no Launchpad , baixei-os e instalei os pacotes usando
sudo dpkg -i <package>
Usando sudo apt-get update e sudo apt-get -f install , confirmei que apt funciona como esperado novamente.