package management - How do I deal with "unauthenticated sources" errors in the Software Center?

Any install that I'm trying through the Software Center is telling me:

Requires installation of untrusted packages: The action would require the installation of packages from not authenticated sources.

I did an apt-get update from the command line, then removed the software sources that the keys were bad from (PPAs I added myself), and unchecked them in the software sources for software center, but to no avail. I can't install anything from software center anymore - only> from the command line with apt-get.

Is uninstalling/installing the only option? I don't want to break other PPAs that I have.

Additional information:

Here's a paste from apt-get update:

Reading package lists... Done
W: GPG error: http://ppa.launchpad.net oneiric Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY B725097B3ACC3965
W: GPG error: http://us.archive.ubuntu.com oneiric Release: The following signatures were invalid: BADSIG 40976EAF437D05B5 Ubuntu Archive Automatic Signing Key 

I've tried apt-key update, and there was no effect (two keys unchanged).

The output of apt-get update and apt-get upgrade, and the contents of /etc/apt/sources.list, can be found in this pastebin post.

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

Update:
This might not help in some later versions, which might require alternative solutions like the one in the other answer, or this one that seems to do the job in some cases under Ubuntu 16.04:

sudo apt-get update
sudo apt-get dist-upgrade