I hope it's not this common bug:
http://fedoraproject.org/wiki/Bugs/Common#DNS_resolver_not_reliable
I have the same problem with yum not working and I'd say it is definitely DNS trouble. 'Ping' and 'host' do work, but ssh, yum and Firefox do not. I can ping one machine by its name, but if I try to ssh into it a second later, ssh cannot resolve the address. The DNS server is local to our network, so I know it's bind-9.3.4-6.0.3.P1.el5_2 running on CentOS 5.2.
This is with kernel-2.6.29-0.93.rc3.git10.fc11.i586 glibc-2.9.90-3.i686 in the F11/Rawhide system.
Mikko