Other monks have pointed to problems with MS telnet server's implementation. My guess is that you've not reached these problems yet as the Telnet server that comes with win2k & up uses funky Microsoft only authentification by default
For win2K (and probably XP) you need to look in the local microsoft help for "telnet admin" and follow the bouncing wizard to change authentication from "NTLM" to "plain."
If MS telnet server doesn't work w/ Net::Telnet and you hae to install another server anyway, consider a ssh server as you won't be passing passwords over the net in the clear. Every cracked box I've seen or heard of has had a password sniffer installed