A second CPU or core will help tremendously. We used to use single-CPU boxes for this and we noticed that traffic sometimes stalls when the machine has to do some task other than NATting, such as expiring idle flows. Having a second CPU or core will help keep latency much more uniform.
We have a few dual 3.2Ghz Xeon boxes (not the ones based on Core, the older ones) that NAT/FW across two GE interfaces. They do quite well up to about 300Mb/s, then we start to see issues. We believe the issues are due to overloading the NB-SB link. A more modern mobo probably wouldn't have this problem.
Since we are talking about PC Routers... 300Mb/s is a limitation we've seen before... especially related to Interrupts overwhelming the system. Modern ethernet cards (non-interrupt based) and a modern OS with support for all of their offloading and zero-copy functions will improve this greatly. Current FreeBSD is signficantly faster than current Linux implementations for this kind of work. But (as I told the OP privately) 45mb/s is a joke and doesn't really need anything more than a 400mhz P-II with two Intel EtherExpress cards and 1GB of RAM. Even for 4,000 downstream connections. A few $200-$300 L3 switches can do this just as well. Deepak Jain AiNET