@spinlock: você nunca voltou para reivindicar sua resposta, mas as regras de acesso me pareceram a primeira possibilidade. Eu definitivamente recomendo que qualquer pessoa que use o EC2 gaste um pouco com o pessoal do Security Groups no começo, é poderoso e muito útil. Para o googling de qualquer pessoa, a resposta do spinlock é:
OK, I figured out where I went wrong. When I created the ec2 instance, I chose "quick launch" because I figured I just needed a simple unix that had sshd running on it. The problem is, this creates a separate security group named "quicklaunch-1".
Então faça isso:
localhost$ ec2-authorize quicklaunch-1 -p 5000