Some debugging approaches:
Have you verified that sshd is actually running.
e.g. ps aux|grep sshd and netstat -nltp|grep 22 (as root)
Assuming sshd is running we want to see the network traffic and what is happening in the server's sshd process and the client ssh process:
Can you ssh to the host from loclhost?
Turn up the ssh logging in /etc/ssh/sshd_config and check the logs.
tcpdump -i any tcp dst port 22 and src host <ssh_client_ip/host> on server host
tcpdump -i any tcp dst port 22 and dst host <ssh_server_ip/host> on client host
Attach strace -F -p <listening sshd process pid> to the listening instance of sshd on the server and see what is happening.
ssh into the server, running the client from strace, i.e. strace ssh <user>@<host> and see what is happening
Also stop the sshd service on the server and run the sshd daemon from the command line in debug mode. e.g.:
service sshd stop;pkill sshd
sshd -d3
or
service sshd stop;pkill sshd
strace sshd -d3.
The -d3 runs sshd with a high debug level and stops it detaching/forking. I.e. it will be the only instance running and the output should go to your terminal
You might also want to use the -oLogLevel=DEBUG on the client command line to make it noisier.
If you are using keys for auth check the dir that your keys are in e,g, ~/.ssh hace sufficiently private perms. e.g chown -R ${USERID}. .sshd; chmod -R 700 .sshd.