Hola
Que distribucion y version de Linux estas usando?. En las versiones recientes el acceso via telnet viene deshabilitado por defecto y usamos conexion via SSH. Si es tu caso, prueba con el PuTTy y en la pantalla donde te pide los datos veras la opcion para elegir "Connection Type: SSH", colocas tus datos de IP o hostname y listo.
La primera vez que te conectas aparecera un mensaje indicando que no existen llaves para tu host (Win XP), simplemente Yes y luego solicitara user/passwd
Saludos