All NICs on all machines involved report exactly the same:
negotiated 100baseTx-FD flow-control, link ok
We've also checked ifconfig on all interfaces, and no errors, dropped packets, overruns, nor collisions have been recorded.
Great! Is your upstream device also able to talk at 100 Mb/s?
You might also try running some point to point bandwidth tests with iperf http://dast.nlanr.net/Projects/Iperf/ to try and isolate which machine(s) are having issues. ntop http://www.ntop.org and iptraf (included in CentOS) can also be useful to monitor bandwidth/throughput as well.
Barry