cpu needed to NAT 45mbs

I do the networking in my house, and hang out with guys that do networking in small offices that have a few T1s. Now I am talking to people about a DS3 connection for 500 laptops*, and I am bing told "a p4 linux box with 2 nics doing NAT will not be able to handle the load." I am not really qualified to say one way or the other. I bet someone here is. * for wifi, going to be using this system: http://wavonline.com/vendorpages/extricom.htm March 13-17 (testing a week or 2 before) for PyCon in Chicago. If anyone wants to see it in action, etc. drop me a line. Carl K