See this faq entry: FAQ: Unable to connect to IRC server (VPS/shell)
From the post above I gather you followed step 1, 2 and 3.
Did you check step 4? The firewall. To quote the FAQ:
Check the firewall
If you cannot connect by IP then you need to check the firewall of the server. Consult the documentation for your Linux distribution or your non-Linux OS.
On some VPS providers like Amazon, you need to configure the firewall in your admin panel as well (these are called Security groups on Amazon EC2).
It's very likely to be the problem. Ubuntu often ships with 'ufw'.
As for your telnet error..
could not resolve 127.0.0.1:6667/telnet: Name or service not known
..that is just because you need to 'telnet 127.0.0.1 6667' and not 'telnet 127.0.0.1:6667'.
I suspect telnet to 127.0.0.1 (with the correct syntax) will connect fine. The firewall is just blocking external connections.
It it's on a hosted server, you should have been given an IP that you need to bind to. On a hosted Enviroment, you should NEVER bind to *.
This is true if it's a shared shell with other users on it. It's not accurate for a VPS or "root server", which I suspect he is using.