Isso funciona como esperado em um sistema CentOS que eu tenho que entregar
telnet> set termdata
Will print hexadecimal representation of terminal traffic.
telnet> open localhost 22
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
SSH-2.0-OpenSSH_5.3
> 0x0 5353482d322e302d4f70656e5353485f352e330a
e em um sistema Ubuntu eu recebo os mesmos resultados que você.
set termdata
Will print hexadecimal representation of terminal traffic.
telnet> open localhost 22
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
SSH-2.0-OpenSSH_5.9p1 Debian-5ubuntu1
Isso pode ser um bug.