O que pode está acontecendo, e tenho quase certeza de que é isso, é que na sua empresa deve ter um Proxy, ou um firewall, que geralmente é um servidor (uma máquina física) que esteja bloqueando o tráfego para portas 22, e outras caso a empresa julgue necessário, ou ainda o provedor de internet pode está fazendo esse bloqueio.
Já sobre você ter que deixar os IP como Anywhere, o que acontece é que como você está usando uma máquina virtual dentro do virtual box, ele recebe outro IP, então você indicou o IP da sua máquina física, porém no momento da conexão o IP que vai querer se conectar com a máquina EC2 é outro IP, ou ainda o provedor de internet pode bloquear isso, as vezes isso acontece, comigo aconteceu algumas vezes e também tive que deixar como Anywhere.
Espero ter esclarecido todas as suas dúvidas!