This issue trips me up all the time.

rpm-5.0 (as currently in CVS) enables pubkey retrieval using HKP.

Which means that even simple commands like "rpm -qa"
will be subject to network timeouts while an automated
pubkey retrieval is undertaken.

Note that the behavior is improved in rpm-5.0 on linux because of
"negative result" caching using keyutils, but I'll leave that for
the newer! better! bestest! feature hype with the rpm-5.0 release.

Meanwhile, do this to disable HKP pubkey retrieval:

     echo "%_hkp_keyserver %{nil}" >> /etc/rpm/macros

The other way to avoid network timeouts is to ensure that all  
necessary pubkeys
are imported using --import.

hth

73 de Jeff