Hi David,
I'm not an expert on networking either but I have experienced a similar problem that you described.
Whenever I would telnet or ftp to my Linux box from my desktop machine it would take sometimes up to 30 seconds to connect. What I finally figured out to solve this problem was to add an entry to my /etc/hosts for my desktop, for example:
192.168.1.27 desktop.internal
Like I said, I'm no expert but what I think happens is that when you telnet or ftp in the server tries to resolve the client's ip address. So the waiting you are experiencing is the server trying to figure out who you are.
So, make sure that everyone in your office is defined in your DNS (If you're running it) or in your /etc/hosts file.
Hope that helps,
Jon