Hi there,
I had a similair question about a month ago, Razbot helped a great deal. Pmfirewall sorted my problem's out (on a very simple LAN - no sub-nets). You've maybe tried this though.
If you fancy trying it the Pmfirewall programme can be found at
http://www.pointman.org/
It is dead easy to set up and worked when other scripts and firewalls failed (including the one on the RH site and Firestarter). It sets up the IP masquerading for you (my IP is dynamic and it copes with that).
Just a thought ,
Best luck
Mike