I have rooted my phone, but why can't I Telnet?
AFAIK, mostly port 1-1024 on android phone are reserved for system, so the application other than system must use port > 1024.

I never use telnet, but I used ssh frequently to remote my phone, I use SSH server on phone using http://teslacoilsw.com/quicksshd maybe you can use ssh as an alternative to telnet.