[CentOS] Performance of CentOS as a NAT gateway

> 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