If you've updated to at least 10.0.1, the 'Allow remote login' option in the Sharing preference turns on ssh instead of telnet, for security reasons. This means you have two choices, either start using ssh (which offers more than telnet, since it can also securely copy files via scp as well as secure logins) or manually turn on telnet if you absolutely must have it.
To turn it on, you need to open a Terminal window and use a text editor (vi, pico, or whatever) to edit /etc/inetd.conf as the root user (so run the text editor with sudo). Find the line:
#telnet stream tcp nowait root /usr/libexec/tcpd telnetd
and remove the # from the beginning of it. Once saved, run,
kill -1 `cat /var/run/inetd.pid`
to restart inetd, and telnet will be open for incoming connections.