Parece que desde o Ubuntu 16.04, o iptables-persistent foi substituído pelo netfilter-persistent. O pacote ainda existe e instala automaticamente o netfilter-persistent graças a uma dependência. É possível usar o seguinte comando para iniciar o firewall.
sudo service netfilter-persistent start