It is highly probable that FC4 is flawed. Look there for config
http://www.linux-noob.com/forums/ind...showtopic=1644
There are probably other firewall softwares you could install from Fedora (via Anaconda, or Yum?). That's what I'd do, install another firewall. On Linux they all work with IP tables.
Do you have a router? If so, just enable the firewall from the router, enable UPnP on it and leave off the firewall on your machines. That's what I do at my home with Mac, Linux and Windows. It is also more secure than software firewalls.
Ciao