Not sure what you mean. Telnetd should be running on the machine that you are trying to connect to. Otherwise there's nothing at the other end to "answer" your telnet connection. It does not need to be running on the machine that you are connecting from.
Also the machine your connecting to should not be blocking port 23 (the standard telnet port).
If possible, go to the machine you wish to connect to and check that telnetd is actually installed (it's often not by default). Then check it's actually running. How you do this depends on what version of Linux/BSD/Unix/Whatever you might be running.
Also, unless you absolutely have to use telnet consider using something more secure like SSH.
Edit: I've just noticed from your original post that you're running Ubuntu.
Install telnetd with
Code:
sudo apt-get install telnetd
If it installs then it should auto start. If not it can be restarted with;
Code:
sudo /etc/init.d/inetd restart
Then while still on that machine you can check it's working with
However, keep in mind that telnet it horribly insecure. Consider using something else if you can.