http://subtech.g.hatena.ne.jp/secondlife/20090710/1247208362 というエントリがあって、この対処をしていたのですが、この度さらに多くのバックエンドを対象にコネクションをはろうとしたところ、全くうんともすんともいかなくなったので以下の対処をしました。

capistrano/configuration/connection.rb を書きかえるのですが

        threads = Array(servers).map { |server| establish_connection_to(server, failed_servers) }
        threads.each { |t| t.join }

となっている部分を

        i = 0
        threads = Array(servers).map { |server|
            p [i+=1, servers.length, server]
            establish_connection_to(server, failed_servers).join
        }
        #threads.each { |t| t.join }

のようにし、シーケンシャルにコネクションをはるようにしました。ついでにプログレスと対象サーバを出すことで安心感を演出しました。