This may sound stupid, but finish reading.
Add more RAM.
The routing table and rule table gets loaded into memory. So as your LAN grows and you add more rules, the size of these grow quite quickly. I dont have alot of experience per se with Linux firewalls, but I have come to worship OpenBSD, and pf (the packet fitler for OBSD) has these limitations.
IF you dont mind my asking, how many rules are getting applied for how many users? And how much RAM? All in all, pump as much RAM as humanly possible in the firewall/gateway. I had for <75 rules 64 MB in the gateway. no problems whatsoever. The bridge I built, had less, 32MB and substantially less rules ( <20 ). Neither have had problems, nor any since my layoff (my manager is a friend of mine, and is rather clueless to UNIX. He will not hesitate to ask, since I built it).