I had some trouble getting my VPN to work with Firestarter, so I’ll post this simple solution I found after some googling.
Go to Preferences->Network Settings.
Choose Ethernet Device (eth0) (yours may be different) as Internet connected network device.
Choose Routed IP Tunnel (tun0) (yours may be different) as Local network connected device.
Place a check mark in Enable Internet Connection Sharing box.
Stop and restart Firestarter.
Originally found here.