Encontrou uma solução que funciona com o Firestarter.
Eu uso o OpenVPN, então eu abri /etc/firestarter/user-pre
e adicionei as seguintes linhas:
# Allow traffic on the OpenVPN inteface
$IPT -A INPUT -i tun+ -j ACCEPT
$IPT -A OUTPUT -o tun+ -j ACCEPT
Então reiniciei o firewall. Pará-lo e iniciá-lo na interface do Firestarter pareceu ser suficiente.
A solução foi aqui .