I had the same problem, but with libnss3, libnss3-nssdb and libnss3-1d. I had installed some packages in the libnss3 family, but not all, and they appear to be interdependent on each other. In other words, I had some version mismatch and was stuck.
apt
couldn't do anything because of unmet dependencies, so the guides suggesting ppa-purge, or downgrading from apt-cache
using Synaptic (which I don't have installed) didn't help much. Some of the solutions I did find would mean that roughly 100 packages, including everything Java-related, every browser, almost everything related to GUI, would be removed.
Here's what I did in the end. It might break your system even more, so proceed with caution and at your own risk!
I found the correct packages (the version I had installed prior to the debacle) on Launchpad, downloaded them, and installed the packages using
sudo dpkg -i <package>
Using sudo apt-get update
and sudo apt-get -f install
I confirmed that apt
works as expected again.