Pode não ajudar na situação, mas eu vi alguns casos em que a reinicialização no EC2 fica 'paralisada'. Se você fizer um "reset" na VM e, em seguida, recuperar os logs do sistema, isso poderá alterar o comportamento. Certifique-se de que os logs sejam do segundo boot e não do primeiro - eles tendem a atrasar as atualizações.
Outra coisa a verificar é ter certeza de que a instância está respondendo no IP. Parece que você está recebendo uma conexão recusada acima, o que parece que a instância está ativa, mas o SSH não está em execução ou tem firewall, mas certifique-se de que a instância foi totalmente reinicializada.
Você também pode tentar abrir todas as portas de um sistema de teste e ver o que o 'nmap' mostra: quaisquer outros serviços que estejam respondendo na instância.