Non ci hai detto la cosa piu' importante, ossia qual e' il messaggio di errore che ottieni, ne' hai riportato eventuali log del server, comunque potresti aver bisogno di:
a. configurare il NAT sul router
b. configurare il firewall su router e debian in modo da non droppare il traffico in input sulla porta 23
c. stai facendo il login come root (cosa sconsigliata)? In questo caso dovresti modificare il file /etc/securetty.

Comunque se non e' un problema, consiglio di usare sshd al posto di telnetd. Se poi hai dei motivi particolari per entrare in telnet, posta i log del server e i messaggi d'errore del client (timed out, connessione rifiutata, ecc.) e vediamo di aiutarti.
Sai usare uno sniffer?