Eu verifiquei minhas tabelas de roteamento usando
route -n
As rotas sugeriam que os pacotes vindos da eth1 (interface com o ip público) estavam sendo enviados para a eth0 (interface tendo o ip privado) e estavam sendo descartados.
Depois disso, foi apenas configurar as rotas certas.