Try changing the terminal type in your telnet program.
Terminal->Preferences
True Story:
I wrote a Telnet application (a minimud) a couple of years ago and just couldn't figure out how to get my telnet app to connect to the server (running on the same machine). I tried for about a week and then gave up in disgust.
I came back six months later to have another crack at it and it worked perfectly first time!
Very strange! (I've heard of bit rot (where a program degrades over time), but this was the reverse. Spooky)