Nesse caso específico, o problema era que o balanceador de carga elástico estava configurado para ser executado em várias sub-redes, e algumas das sub-redes não eram acessíveis publicamente e, portanto, algumas solicitações estavam sendo roteadas para um IP incorreto.
A confusão veio porque entendemos mal o que a configuração de sub-rede no ELB significava.
Portanto, verifique suas sub-redes!