Why does Software Update and Add/Remove Software claim all packages are untrusted?

Solution 1:

I think this Bug report is the very problem you ran into, caused by the installation of PackageKit-0.6.21-1.fc16.x86_64:

Bug 771746 - Software Update claims all packages are untrusted 

For reasons unknown, any attempt to use the Software Update or Add/Remove
Software tools since Dec 31st results in an 'Authenticate' dialog. The text is 

"The software is not from a trusted source. Do not update these packages unless
you are sure it is safe to do so."

Clicking on details gives the following:

Action: org.freedesktop.packagekit.package-install-untrusted
Vendor: The PackageKit Project

Testing indicates this dialog occurs for *any* package, from all the default
repositories. I do not know why Software Update wants a root password as no
changes to the repository configuration have been changed.

The fix is to upgrade PackageKit (and PackageKit-glib) to PackageKit-0.6.21-2.fc16 or newer. Since you have a 64-bit Fedora system, be sure to install both the 32-bit and 64-bit versions of PackageKit and PackageKit-glib.

yum update PackageKit-0.6.21-2.fc16

or simply

yum update PackageKit

You could also download and install the updated rpms for PackageKit and PackageKit-glib (both i686 and x86_64 versions) from this site.