ssh: connect to host HOSTNAME port 22: Connection timed out

I have trouble connecting to a server with ssh from my Lubuntu 14.04 computer, although it can be done from other machines. I can't get to the address online either (others can).

Am currently using a 3G network from my phone, but this doesn't seem to be the problem as I can connect to the server using another computer with the same 3G connection.

This is my attempt to connect:

root@Elizabeth:/# ssh USER@HOSTNAME
ssh: connect to host HOSTNAME port 22: Connection timed out

UPDATE: Saw that ping HOSTNAME renders the wrong IP-address, so I guess this could be a clue to what's wrong. Any way to solve that? I can get around it though by doing ssh USER@IPADDRESS, as suggested to me in a comment.

Some further info below, if it's useful. I'm new to working with servers and networking, so do say if there is other information needed to say what is wrong.

root@Elizabeth:/# nm-tool | grep "DNS"
DNS: 172.20.10.1
DNS: 172.20.10.1

root@Elizabeth:/# nslookup HOSTNAME
Server:        127.0.1.1
Address:    127.0.1.1#53

Non-authoritative answer:
Name:    HOSTNAME
Address: IP-address # correct IP-address for HOSTNAME

root@Elizabeth:/# ip route
default via 172.20.10.1 dev eth1  proto static 
172.20.10.0/28 dev eth1  proto kernel  scope link  src 172.20.10.3  metric 1 
172.20.10.0/28 dev wlan0  proto kernel  scope link  src 172.20.10.5  metric 9

Solution 1:

To properly test your ssh use ssh user@ipaddress. If that fails, the issue is something deeper like the connection.

Solution 2:

Allow ssh to ufw will solve the problem. Run the below command to allow.

sudo ufw allow ssh