I've always had a problem with fresh Redhat installs. Redhat likes to ask you your hostname when it's installing and then in /etc/hosts it does:
127.0.0.1 localhost localhost.localdomain myhostname
Which Condor does not like. Just delete the myhostname part.
- Ian