it would be nice to know the general topology of the network, in case there's a botleneck. Also, how much traffic are you expecting to go through the Linux box? How fast is your WAN. How much bandwidth is being used on you WAN?
Ma'b your internal network is fine and the WAN is getting hammered.