Resolvi isso com a ajuda do suporte técnico da AWS. Aqui está a informação para futuros novatos como eu:
O problema era que o iptables estava em execução na instância B e não permitia tráfego. Aprendi que existem dois níveis de firewall para instâncias do EC2: grupos de segurança (gerenciados no console da AWS) e iptables (gerenciados no host). Existem razões para usar o iptables, por exemplo link
Most of the time you don't need to worry about using a host-level firewall such as iptables when running Amazon EC2, because Amazon allows you to run instances inside a "security group", which is effectively a firewall policy that you use to specify which connections from the outside world should be allowed to reach the instance. However, this is a "whitelist" approach, and it is not straightforward to use it for "blacklisting" purposes on a running instance.
No meu caso, não preciso de um firewall no nível do host, por isso, desliguei o iptables:
sudo service chkconfig stop
sudo chkconfig iptables off
Aqui estão alguns resultados relacionados aos comentários postados nesta pergunta:
- conectando-se ao ip privado trabalhado
- conectando-se ao nome DNS privado trabalhado
- conectando-se ao ip público trabalhado
- conectando-se com o EIP público trabalhado
- conectando-se com o DNS público funcionou, mas como Chad Smith disse em sua resposta DNS retorna o IP private para este nome
A razão pela qual isso funcionou para mim em uma instância diferente é que a imagem que usei naquela instância não executava iptables - cada imagem é diferente. A imagem que usei neste caso usava o iptables para proibir todas as conexões, exceto o SSH.