EC2: telnet one instance from another instance

It sounds like you don't have an ingress rule allowing TCP connections on the right port in any of the instance's (or ENI's) Security Groups. ICMP is a different IP protocol that allows software such as ping to work. But it would not allow a telnet session to work.

Most linux distros do not come with telnet server installed. Have you verified the telnet server is running on the instance you want to telnet into? What linux are you using? I'm a bit confused as to which ports are open on "ICMP ALL Ports." Telnet runs on port 23 and is not ICMP traffic. Try adding port 23 to your security group's inbound rule.

Is there a specific purpose for trying to use Telnet?

It has been considered bad practice to use insecure protocols like Telnet for a long time now because they transmit plain text over the network. I found an AWS article from 2008 specifically recommending use of SSH over Telnet.

SSH is secure by design and comes pre-installed/running on nearly every flavour of Linux. Another advantage is the ability to use SSH Keys for authentication saving the need for/admin of passwords.

Add an ingress TCP rule for the port you are trying to telnet into. For e.g. to telnet to port 8080, add TCP inbound 8080 to the Incoming Security Group of the server you're telneting into. Then from the source server type:

telnet <target server IP> 8080