Isso soa como um problema de firewall para mim. Você pode verificar se a porta 22 está aberta na sua instância? Eu nunca usei a Amazon como um provedor, mas eu encontrei algumas instruções para criando um grupo de segurança que parece ser a direção certa.