[CentOS] Performance of CentOS as a NAT gateway

We have a single 3GHz P4 box w/2GB RAM running CentOS 3.8, acting as a
gateway, which serves multiple IP address, having one virtual
interface for each IP, e.g., eth0:1, eth0:2, etc.  These
interfaces/IPs are on the public internet.  Each of these IP addresses
is the NAT address for a different small LAN.  All of these LANs are
connected through a single Linksys 100Mb switch, to eth1 on the
gateway.  Thus, in case it's not obvious from that description,
traffic from LAN X travels through through the switch to eth1 on the
gateway, where iptables translates it to the IP address of eth0:X and
thence out to the net.

The gateway is totally idle except for handling these NATs; no other
processes except the usual OS bookkeeping.  All NIC and switch
hardware involved is 100Mb.

This all works, but we're experiencing network congestion somewhere.
The LANs appear to become saturated when only about 10Mb of total
traffic is passing through the public IPs.  That is, we seem to be
losing almost 90% of our capacity somewhere in the translation.

Before we attempt to sweep this under the rug by using Gb
NICs/switches for the LANs, we'd like to understand what's going on.
I can't find any recent statistics for Linux NAT performance, but the
older stuff I can find (e.g. 50k packets/sec for a P3-450Mhz) seems to
indicate that the gateway should easily be up to the task of handling
the NAT traffic.  Am I wrong about this?  Is there any way to diagnose
whether the NAT is the bottleneck?  Would we benefit from upgrading to
a newer CentOS (2.6 kernel as opposed to 2.4)?  Or is it more likely
to be the switch, in which case what would be a recommended
replacement for the Linksys?

I can provide more details in private mail if necessary.  Thanks in
advance for any ideas.