Supondo que a instância tenha um IP público anexado (um IP elástico ou não): a tabela de rotas da sub-rede contém uma entrada para acesso à Internet:
0.0.0.0/0 via igw-XXXXXX
onde o igw-XXXXXX é o seu gateway de Internet?
Verifique também se o firewall local não está bloqueando o tráfego.