The reason you should not use telnet over public lines is: it is not encrypted. Practically any sniffer can pick up the x-fered info. Try it out yourself. Setup a terminal server w/telnet running, and setup your packet sniffer.

Run your packet sniffer and then telnet/login to the telnet server.

You will be able to grab everything from that session. I played around a bit with this on my school network. People were telnetting to a linux server instead of ssh. I had a network admin by my side when we did this... so I had permission. We were able to grab any session and usernames and passwords of people. We were able to even see the mail they read and wrote. Pretty scary...

It is ok to use it for connection testing on a private lan. Example. You don't have PuTTY installed but you need to test the connection (7 layers) to troubleshoot a network problem. I will use telnet to confirm connection, but won't enter in sensitive info.

PuTTY will supports encryption and it is simply more powerful. You can connect to and do more with less programs.

Even if you use PuTTY to log into a telnet server, your communication can still be sniffed. The solution? Use SSH.

A quick and sloppy description of the differences between Telnet and SSH.
Taken from: here.
Telnet vs. SSH

For many years telnet has been the means by which users logged onto remote computers. But telnet transmits data in plain readable text, which is readily intercepted by hackers.

There's now a better choice: It's SSH (which stands for Secure Shell). SSH clients work just like traditional telnet clients. You can use SSH to do anything you might typically do with telnet and with the assurance that your password and other sensitive information are secure.
g00n: We must have been typing at the same time. Good explination... exactly what I was thinking. I just didn't go into so much detail.