Does AWS not allow outbound SSH connections?

I was wondering if Amazon Web Services disallows outbound SSH connections from public facing EC2 instances? I have an SSH Bastion on a public subnet with an Elastic IP setup to where I can can successfully tunnel connections into my VPCs but when I create a Security Group rule to allow outbound connections to a remote server and try to make a connection I get:

ssh: Connection timed out

I've done some searching, and found this question unanswered:

https://forums.aws.amazon.com/thread.jspa?messageID=205579

Edit: I can SSH from the SSH-Bastion but ONLY to other EC2 instances that belong to me. Connecting to an external server not on AWS is currently not working for me.

Edit2: I can also make outbound connections to the internet through an Internet Gateway. Running works

curl www.google.com 
telnet www.google.com 80

The outbound security rules for the bastion look like this:

22 (SSH)    [internal AWS Private subnet range]
22 (SSH)    [external linode ip]
80 (HTTP)   0.0.0.0/0
443 (HTTPS) 0.0.0.0/0