SSH Connection refused

I would suggest the following in addition to the answers already present. Ensure you have some way to restore you're firewall after carefully checking its ruleset.

Disclaimer: if this device is an internet facing machine, this will drop all firewall protection from all interfaces, and could lead to your box getting owned.

# iptables --flush
# iptables -P INPUT ACCEPT
# iptables -P FORWARD ACCEPT
# iptables -P OUTPUT ACCEPT
# /etc/init.d/openssh-server restart

Then retry connection via ssh, if that fails check /var/log/auth.log.

You can also use

# lsof -i TCP:22 

to see if the ssh port is opened and what IP address it's listening on.

edit: re: update, that doesn't appear to be ssh related (it seems to be in relation to sudo privilege elevation.

try tail -f /var/log/auth.log while attempting to connect via ssh.

Connection refused mean that the connection was explicitly rejected by either a firewall or the daemon it's self.

A normal connection would look something like this:

Mar 23 13:32:32 <hostname> sshd[20100]: Accepted password for <user> from xxx.xxx.xxx.xxx port xxxxx ssh2
Mar 23 13:32:32 <hostname> sshd[20102]: (pam_unix) session opened for user <user> by (uid=0)

While an authentication failure will look like this:

Mar 23 13:35:54 <hostname> sshd[20177]: Failed password for <user> from xxx.xxx.xxx.xxx port xxxxx ssh2

If it were blocked by sshd for some reason, that will be eluded to in the auth log, if it were blocked by the firewall (note the firewall may be on the host, client or somewhere in between) you'll see nothing.

Get back to us if that's the case, from there it'll be tcp dump on the client, server and any intermediary routers.

Well, it could be that the ssh server is down for whatever reason - one way to check for it is using netcat - netcat should yield some sort of response. I'd also give it a shot from another ip address to be safe.