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:
As an FYI, you generally want to be running SSH and NOT telnet since SSH is secure (while telnet is not)--especially if you're on a fast connection with a static IP. There are clients for SSH'ing to your computer available for just about every platform, too. My $.02: use SSH.