Só para ficar claro, você tem duas tabelas de roteamento, uma instância do NAT e um Gateway da Internet, certo? A rota padrão (0.0.0.0/0) para a tabela de roteamento usada pela sub-rede pública deve ser para o Gateway de Internet (igw) e a rota padrão na tabela de roteamento usada por sub-redes privadas deve ser a instância do NAT. Às vezes, a AWS configura isso para você automaticamente quando você usa o assistente, mas presumo que esteja configurando-o manualmente, já que você está configurando a instância do NAT manualmente.