tcp_wrappers has lots of compile-time options, including ones which specify how enthusiastic it should be about performing (especially reverse) DNS lookups. I'd quite like a /usr/sbin/tcpd-no-dns in the package which won't do DNS lookups by default.
Please verify this with a newer version of Red Hat Enterprise Linux or Fedora Core and reopen it against the new version if it still occurs. Closing as "not a bug" for now.