Linux – Router and Firewall with IP Accounting

I'm working on a project to replace my organisation's aging Slackware gateway/router/firewall machine, which will have several hundred users behind it. Previously we used rc.firewall but we are now looking for something more modern and easily configurable. The current requirements are (hopefully this is all of them, but I may have missed something):

• Act as a gateway router & firewall
• Port forwarding to a Terminal Server
• IP/traffic accounting, i.e. ability to view breakdown of external traffic by originating address (preferably accessible via SNMP or rrdtool to integrate with cacti)
• Possibility of acting as a PPTP server & routing these connections
• Is not an out-of-the-box Cisco product (don't have the finances or support to maintain it)
• edit: transparent proxy cache

I'd prefer to use Ubuntu or some other Debian-based distro but something that integrates everything we're looking for is certainly an option if it offers all the desired features and is easy to configure.

Is there a simple set of packages that will provide me with the Firewall & Accounting features, or am I best served with a custom-built distro / other solution?