I got:

Retrieving key from file:///etc/pki/rpm-gpg/RPM-GPG-KEY-redhat-release


The GPG keys listed for the "RHEL6 Server" repository are already installed but they are not correct for this package.
Check that the correct key URLs are configured for this repository.

Fix:

Run the update command with -v. You will get the same output, but before the error, you will get the name of the last checked package. That package has an error. If you manage your own repo, you might want to download it again. Verify the key with:

# Good:
$ rpm --checksig -v policycoreutils-2.0.83-19.39.el6.x86_64.rpm 
policycoreutils-2.0.83-19.39.el6.x86_64.rpm:
    Header V3 RSA/SHA256 Signature, key ID fd431d51: OK
    Header SHA1 digest: OK (c5130e430f5ba2d2b2721a011414910b819ffd29)
    V3 RSA/SHA256 Signature, key ID fd431d51: OK
    MD5 digest: OK (b165051b831e3285628a784adfd4ab20)

#Bad:
rpm --checksig -v policycoreutils-2.0.83-19.39.el6.x86_64.rpm
policycoreutils-2.0.83-19.39.el6.x86_64.rpm:
    Header V3 RSA/SHA256 Signature, key ID f21541eb: NOKEY
    Header SHA1 digest: OK (c5130e430f5ba2d2b2721a011414910b819ffd29)
    V3 RSA/SHA256 Signature, key ID f21541eb: NOKEY
    MD5 digest: OK (b165051b831e3285628a784adfd4ab20)

Notice the NOKEY part.