Problema resolvido:
Eu usei o nome de usuário errado. Tentar fazer o login como root mostra o seguinte erro:
Please login as the ec2-user user rather than root user.
Aparentemente, a convenção de nomes de usuários não é consistente entre as AMIs da Amazon - algumas usam ec2_user, algumas ec2-user.