Telnet Latency

We have a small network with several flavors of UNIX (AIX, HP, SCO) and a small NT 4.0 domain. Physical network is ethernet and hubs. A couple of weeks ago we started having problems with telneting to the UNIX hosts. When we try to connect, it takes1 to 2 minutes before we get a login prompt. Once we get the login prompt it works fine from there.

It does not matter which client or which UNIX box we try. It is the same using Windows Hyper -terminal or WRQ Reflections.
It does not matter ifwe use host names or IP addresses. There is no trouble pinging the boxes.
Does anyone have any ideas, or can you point me to some tools or troubleshooting resources for telnet?
Thanks!