Como sugerido por @dirkt, parece que conntrack não funciona bem com uma bridge. Portanto, as regras do iptables que não requerem parecem funcionar em uma ponte, mas não na NAT.
Problema resolvido assim que configurei meu firewall como um firewall de camada 3.
No caso de outros se interessarem: Pesquisei bastante na Web se era possível usar um firewall transparente de camada 2 com NAT, mas nunca recebi uma resposta direta.
site ebtables sugerimos que é possível:
bridge-nf code makes iptables see the bridged IP packets and enables transparent IP NAT.
Eu nunca descobri que comando ebtables faria isso funcionar.