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.
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.