Good news is that you don't need Firestarter to work with your firewall, as it's just a front-end. You can use iptables
If reinstalling didn't help, I would try a second time by first removing it (along with all
of it's config files), cleaning all package cache and then re-downloading and installing it from the reposities. If that does not help then I assume it's a bug in the package or something and ought to be fixed soon (if it's general, not just you).
the latter as root shows your current firewall configuration. First command shows you how to use iptables. I prefer that way over Firestarter-like programs but if you like a nice GUI more than command line, it's your choice.