I tried to install a couple of updates on my work laptop, running Ubuntu 12.04, a minute or two ago when prompted by the update manager, and I got the "requires installation of untrusted packages" error.
I've since dicovered that there are two ways round this, one is to allow untrusted packages by doing the update as root or via sudo, and saying "y" when asked
Install these packages without verification [y/N]?But I don't like that, you don't know who might be spoofing you with what fake packages. The better way is to rebuild the apt cache. I found the instructions here, I'm claiming no credit for solving the problem, just reproducing them below so that I can be sure to find them again next time I need them. Hopefully some of you who read this in the future will also benefit.
sudo apt-get clean cd /var/lib/apt sudo mv lists lists.old sudo mkdir -p lists/partial sudo apt-get clean sudo apt-get update
Enjoy!