"Connection timed out" sounds like a firewall issue. Try breaking down the connection into the individual steps performed at the network level:
- ping -n $HOSTNAME
- telnet $IP_ADDRESS 22
The ping will test the resolution of the name into an IP and that you can ping that host. If you can ping it, you know you have network connectivity to it. Though not being able to ping it does not mean that you don't have connectivity to it, as pings could be filtered out.
Use the IP address from the ping in the telnet and telnet to the SSH port. If that takes many seconds and reports "Connection timed out", it really does seem like there's a firewall in the way.
As you say, if tcpwrappers was the problem it would likely be as "connection closed unexpectedly" result. If SSH for some reason isn't running, you would get a "connection refused" error.
If you have root access on the server, check the host firewall with
iptables-save | less (or similar if it's not Linux). If it's not there, you'll probably need to have whoever runs the networking check firewalls that may exist there.
iptables-save returns nothing, it may mean that you aren't running it as root. However, it may also mean that there are no rules. If, however, it returns 20 or more lines of output, there is probably a firewall in place.
You can add a temporary firewall allow rule, so you can test to see if the firewall is an issue, by running:
iptables -I INPUT -m tcp -p tcp --dport 22 -j ACCEPT
That would probably allow a ssh connection unless there is some deeper problem with the firewall like a bad NAT rule which is more difficult to diagnose. You could try disabling the firewall with a command like (Fedora/CentOS/RHEL) "sudo service iptables stop" (Debian/Ubuntu) "sudo ufw disable" (though on Debian/Ubuntu you may be running something other than ufw, there's no "standard" that I know of).
That said, one thing you might want to consider is setting up a VPN. That way it wouldn't matter what your remote IP is, you would use certificates or keys to authenticate the VPN connection, and then get a static IP address on the VPN that could be allowed in the firewall and TCP wrappers.