You could try installing such programs as Firestarter (firewall/router/sharing) on your linux box.
It is the easiest way to get your Internet Connection Sharing running with a secure firewall.
Homepage:
http://firestarter.sourceforge.net/
Red Hat 9 RPM:
http://flow.dl.sourceforge.net/sourceforge/firestarter/firestarter-0.9.2-3.i386.rpm
Note: You will need GNOME or at least the GNOME libraries installed to get this working.
I currently run this on my Red Hat 7.2 box as it was the easiest and quickest way to get my connection up, so far after over 12 months I haven't really had a single problem.