Just to add more to the discussion.
Telnet server in Win2k by default supports only NTLM Authentication and the only telnet program that I know supporting this is native to Win2k onwards, You will need to enable plain text auth (From telnet server admin applet) to access it from normal telnet client.
Regards
AFAIK, only NT based Windoze allow you to run telnet as a service.