豊島(東京外国語大学アジア・アフリカ言語文化研究所)です。

> mysql -uuser -ppassword -hhostname -Pポート番号
> の形で接続しています。
> サーバー機のコンソールから同様に接続すると瞬時に
> つながるのですが、別の機械のコンソールからだと、10秒
> 程度かかってやっとつながります。

hostname の look up が timeout している、という事はないでしょうか。
hostname が IP アドレスにするとどうなるのでしょう。

WireShark あたりでパケットを覗いてみると、はっきりすると思いますけれど。