Acontece que o problema era a configuração do Grupo de Segurança depois de tudo.
Eu estava restringindo o tráfego de IP, então apenas meu IP externo podia se comunicar com as instâncias. Presumi que os grupos de segurança não se aplicavam à comunicação entre instâncias, mas eles se aplicam.
A solução também permitia o tráfego de 10.0.0.0/8, que abrange todos os IPs privados EC2 possíveis. Seria mais seguro permitir somente o tráfego de IPs privados específicos, mas isso é um incômodo, pois eles podem mudar.
Isso resolve meu problema por enquanto. Provavelmente, a melhor solução seria utilizar a API da Amazon para ajustar automaticamente as restrições de IP do Grupo de Segurança quando as instâncias forem interrompidas e iniciadas.