I setup Firestarter on KDE and it installed very nicely, however there are some quirks.
I am using dialup on ppp0 (a 56k modem) and I HAVE to start Firestarter AFTER I am connected or northing will happen.
Give this a try.
My other problem is that currently I can only access the net as Root Now. Which is very annoying as you are not supposed to!