EPEL 5 Key not being used by CentOS 5 client

I have a CentOS 5 product, which includes the EPEL 5 repo. The EPEL5 key
has been added and associated with the repo. The client .repo file has
gpgcheck=1.

When I try to install the katell-agent, the EPEL dependencies fail with:

Public key for python-uuid-1.30-3.el5.noarch.rpm is not installed

Strange that the client doesn't get the key from Katello. Any thoughts??