In general, for normal desktop computing behind local networks, running a supplementary firewall such as firestarter is not necessary IMO. This is because, by default all ports are closed and will remain so until you start some kind of server process... most probably ones which you want to use... e.g. samba, ssh. And if you are behind a router or on a LAN the chances of a threat are less.
In my personal use, the only change within a LAN setup is that the interface drops requests (with firewall) as opposed to replying as closed (without firewall). That and you have to manually open ports for the services you want to use.
As for your problem, to me it seems it lies in the fact that firestarter is run as a system service (at boot) and the network is managed by networkmanager. Networkmanager only connects to the network once you log in. Hence firestarter starts first, sees no valid connection and doesn't know what to do.
I think UFW would be a better integrated option on the Ubuntu base. It also has a simple GUI, Gufw. If I remember correctly this is the default setup in the main edition.https://wiki.ubuntu.com/UncomplicatedFi ... tuFirewallhttp://www.ubuntugeek.com/gufw-simple-g ... ewall.html
P.S. if you use UFW, remember to uninstall firestarter or disable it from starting at boot.