@John: Does the affected machine have "nis" on the "hosts" line in /etc/nsswitch.conf? If not then your problem is not the same as this one.
@John: Does the affected machine have "nis" on the "hosts" line in /etc/nsswitch.conf? If not then your problem is not the same as this one.