Hola,
Para las conexiones desde otros ordenadores via telenet ahora las últimas distros de linux usan ssh, que son conexiones seguras (encriptadas), muchas de ellas lo suelen traer ya configurado, se realizan a traves del puerto 22 y funcionan de forma muy similar al antiguo telnet (ssh IP_o_Maquina). El problema es conectarse desde una maquina Windows a una Linux via ssh ya que el windows no lo trae, pero hay una aplicación libre que lo permite y es muy sencilla, se llama putty (www.chiark.greenend.org.uk/~sgtatham/putty/).
En cuanto a tus problemas con el telnet no sé porque pueden ser, bien porque estes detrás de un firewal que tenga chapado el puerto del telnet, está detrás de un router y no tienes configurado el NAT,... hay que tener en cuenta que muchas distros no te dejan validarte directamente como root a través de telnet, te que hacer telnet a la máquina validarte como otro ususario y hacer el su -. Estas son unas de las soluciones que se me ocurren, puede ser que te pase lo mismo si te decides a usar ssh.
Otro posible problema que se me ocurre es que tengas una regla en las iptables que impidan la conexión telnet para ver la reglas usa iptables -L desde un terminal y mira a ver si hay alguna tipo REJECT al puerto 23. En distros antiguas las iptables se llamaban ipchains.
Espero haberte sido de ayuda, un saludo