A instância do NAT é a solução correta para a situação em que você está, mas suspeito que você tenha cometido um erro de provisionamento comum - você tem suas instâncias do servidor da Web na mesma sub-rede que o seu ELB.
É intuitivo fazer isso dessa maneira, mas não está correto, a menos que seus servidores da Web também tenham seus próprios endereços IP públicos.
Eu assumo isso, porque senão não há motivos para que os servidores da Web não respondam a solicitações quando você altera suas rotas padrão - os servidores da Web não falam com os navegadores, falam apenas com o ELB - - então o que tecnicamente quebra quando você muda a rota padrão é que os ELBs não podem mais voltar aos navegadores.
A configuração correta é colocar o ELB em uma sub-rede pública - que usa o Gateway da Internet como sua rota padrão, e os servidores da Web em uma sub-rede privada - que usa uma instância do NAT como sua rota padrão. A própria instância NAT também entra em uma sub-rede pública, é claro.
Consulte acesso à Internet via sub-rede pública da VPC com ELB ligado .
Embora este documento da AWS seja sobre o Elastic Beanstalk, a ilustração ainda é relevante. O ELB é mostrado em uma sub-rede pública, junto com uma instância NAT, e os servidores da Web estão em uma sub-rede privada.
Veja também Por que precisamos de uma sub-rede privada? VPC?