I think you are confusing Firestarter with the actual firewall. Firestarter is just a nice GUI which enables you to add rules to the firewall, which is based on iptables. For example, I needed to add a rule to allow my wife to access a SAMBA share on my PC.
I don't think that seeing the firestarter process running tells you much other than that the GUI is running. If you have enabled the firewall in VASM then doing an lsmod | less will show several modules loaded such as ip_tables and ipt_MASQUERADE, which I presume are the actual firewall.
If you are on a network you can test whether the firewall is doing anything. First ping your PC from another one. Then start Firestarter from a terminal (or from the System menu) and go to Preferences > Firewall > ICMP filtering. Tick the Enable ICMP filtering check box but don't tick any of packet types. Restart the firewall, close the Firestarter GUI and then ping again. You should find it to blocked this time around, showing that the firewall is working.
As for other firewalls, I used Guarddog for a while, but it was a lot more complicated to set up (though it did give very fine control) and it, too, was just a front end for iptables. My guess (hope!) is that Firestarter does the job sufficiently well in the same way as Windows' built-in firewall.
Hope the above makes sense.