Hardware

I am currently running a m0n0wall server and have given out over 2000 IP's.  The load on the system is running very high.  The load is running high because the DNS is being pounded.  I can only assume that with +2000 users that this should be expected.  I am running this on a P4 2.8Ghz with 512Mb of RAM and 20GB hd.  What hardware should I put in place to take the load of +2000 users?

IMO, with 2000+ users, you should probably be looking at more enterprise solutions, such as a Cisco or Sonicwall device.

If you want to keep the m0n0wall, you could always set up a separate DNS server that is equipped to handle the load.

If the local DNS forwarder is being overloaded just make adjustment in the DHCP server configuration, so it hands out leases with DNS servers let's say 8.8.8.8 and 8.8.4.4 - Google public DNS recursors.
After that turn off the local DNS forwarder.
Then add rules permitting the new DNS traffic.

I suppose You're running Your own built m0n0 image?