I fought the same or similar situation for a while now. I am using Mandrake 9.1 with samba, security high.
I found my internet connection sharing was working and my Domain network was not. I watched my startup of Linux and seen 2 things that could be preventing it. iptables and Shorewall were both being started at boot. These are both dealing with firewall. I read, and read, and read all the links to both but couldn't come up with a quick answer on how to fix my problems. Finally 2 things worked.
I researched shorewall and used their tutorial shorewall tutorial
and configured it using my Mandrake installed shorewall (had to change some references dealing with loc verses masq due to Mandrake as it states in the tutorial) Restarted eveything and still had the same problem. If i stopped iptables, my network worked but my ICS didn't. With iptables running ICS worked, network didn't. I knew my problem was there. Did more research
read everthing there. I am a newbie and didn't know how to do half the stuff they talked about.
Did some more searching on these forums and found a link to arno's firewall
downloaded, copied and followed the instructions in the readme file and voila, it all works well now.
None of my research was in vain. I learned alot (almost too much to absorb) as time permits I will be tweeking the settings to better suit my situation.
BTW I did try fwbuilder
as several post had mentioned. The only problem with a GUI is you don't know what it did or how, ie you didn't learn. I was still having some problems using it, that is when I found the link to arno's
Sorry for being so long winded. Hope this helps or solves your problems.
Thank you to everyone who posts on these forums as they have been a God send to figuring things out. Speacial thanks to those that posted the links I posted here. Sorry I don't remember your names, and I have researched enough this weekend.