From my laptop I'm trying to connect to HOST1 and I get:
$ ssh -vvv user@HOST1
OpenSSH_6.0p1 Debian-3ubuntu1, OpenSSL 1.0.1c 10 May 2012
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: Applying options for *
debug2: ssh_connect: needpriv 0
debug1: Connecting to HOST1 [x.x.x.x] port 22.
ssh: connect to host HOST1 port 22: Connection timed out
The ssh daemon on the server is working fine as I'm able to connect to it from other machine.
For instance from my laptop I'm able to ssh into HOST2 and from there I'm able to ssh into HOST1 but it's annoying.
HOST1 is some host I have control of, but it's happening also with github and bitbucket.
This lead me to believe the problem is client side only, but I ran out of ideas.