Это случилось со мной, когда у меня был мост от eth0 до virbr0 (для kvm / qemu). Поэтому, если у кого-то возникнет аналогичная проблема, попробуйте отключить мост (in /etc/network/interfaces), перезагрузите сеть и попробуйте снова. После добавления правил вы можете снова включить мост.
Или просто не используйте Firestarter. Это мертвое приложение, и похоже, что проблема заключается в ошибке в Firestarter.
Другие графические интерфейсы для брандмауэра см .: https://askubuntu.com/questions/111/gui-for-iptables.