Getting long TCP connect latency on connect in a LAN (over a cross!)

I am measuring a time of about 100-150 milliseconds from sending TCP SYN to getting SYN/ACK, between two linux computers connected to the same Cisco switch.
Consider:

• The machines are very powerful, and neither them nor the switch is heavily loaded.
• From analyzing tcpdumps logs on the two machines I see the problem is not in the endpoints but rather in the network itself (the client sees 100-150 ms delay, but the server processes the responses in about 10 ms).
• Only SYN requests are slow. Afterwards, a normal TCP packets gets an ACK right away.

So, my questions are:

• Am I right to think this is way, way too much?
• What latency should I aim for?
• What can I do to further diagnose and solve the issue?

Edit – We've taken the switch out of the equation. The two computers are now connected in a cross cable, and we're still seeing the problem. Both are on full duplex, 100 MBPS.