I am having problems with a Red Hat server 2.6.18.
The creation of a new TCP socket takes very long - once it is established it is fine. iptables and selinux are disabled - is there any other service which needs to be stopped?
Oddly enough I see the problem with Windows machines only.
If you are using ssh, add the following to /etc/ssh/sshd_config