Aarrgghh. . . yes, I had the same intermittent problem. In my case, I tracked it down to the update software using several different sites as repositories for update RPMs, and even though Fedora comes configured by default to use those repositories, it apparently only comes configured with GPG keys for SOME of them. Hence, sometimes it works, and sometimes it gives you GPG errors.
I found the solution here
. Briefly, you need to import the GPG keys for all the main repositories:
rpm --import /usr/share/doc/fedora-release-1/RPM-GPG-KEY*
rpm --import http://www.fedora.us/FEDORA-GPG-KEY
rpm --import http://rpm.livna.org/RPM-LIVNA-GPG-KEY
rpm --import http://freshrpms.net/packages/RPM-GPG-KEY.txt
rpm --import http://dag.wieers.com/packages/RPM-GPG-KEY.dag.txt
rpm --import http://atrpms.physik.fu-berlin.de/RPM-GPG-KEY.atrpms
Once I did that, the updater worked consistently, with no more GPG errors.