[topdog]

The last time i had a similar problem i used strace to see what system calls telnet was making, it turned out to be nscd which had cached the wrong name,

Do you have nscd running ?

Running strace will help you to get to the bottom of the problem.