Comment 75 for bug 122560

Update: I finally resolved it, I'm not sure exactly how, but some of the things I did were:

sudo dpkg-reconfigure synaptic
sudo dpkg-reconfigure update-manager
sudo apt-get update
sudo apt-get dist-upgrade
sudo dpkg -C
sudo apt-get install -f

and finally it worked (I had done the "dpkg -C" and "apt-get install -f" many times before, with no success, this time they worked.