I've helped a few people recently who have had trouble getting OpenSSH working properly; I've also had my share of issues over the years. Generally problems with SSH connections fall into two groups - network related and server related. Most of these problems can be fixed fairly quickly if you know what to look for.
Network Related Problems
These will typically be caused by improper routing or firewall configurations. Here are some things to check.
1. If your SSH server sits behind a firewall or router, make sure the default route of your internal SSH server points back to that firewall or router. Seems obvious, but it's common to forget about the return trip packets need to make. This will display your default gateway:
netstat -rn | grep UG
Sometimes the default gateway is just one of your server interfaces, this is OK as long as that interface is directly connected to something that knows how to get back to your client.
2. While you're at it, make sure the incoming SSH packets are actually getting to your SSH server. Tcpdump works very nicely for this, you'll need to be root to run it on the server:
tcpdump -n -i eth0 tcp port 22 and host [IP address of client]
Just replace eth0 by your client-facing interface name. If you don't see incoming SSH packets during connection attempts, it's probably due to a firewall or router access list.
SSH Server Problems
All of these issues revolve around SSH server configuration settings - not misconfigurations necessarily, just settings you may not be aware of.
1. Permissions can be a problem - in its default configuration, OpenSSH sets StrictModes to yes and won't allow any connections if the account you're trying to SSH into has group- or world-writable permissions on its home directory, ~/.ssh directory, or ~/.ssh/authorized_keys file. I typically just make the two directories mode 700 and the authorized_keys file mode 600. The sshd man page suggests this one-liner:
chmod go-w ~/ ~/.ssh ~/.ssh/authorized_keys
2. On Debian or Ubuntu systems, it is possible the keys you are using to connect are blacklisted. This is only an issue on Debian or Debian-based clients, and stems from this now-famous vulnerability in May of 2008. To detect any such blacklisted keys, run ssh-vulnkey on the client, while logged into the account you are connecting from. Debian and Ubuntu SSH servers will reject any such keys unless the PermitBlacklistedKeys directive in the /etc/ssh/sshd_config file is set to no. I don't recommend you actually leave this security check disabled, but it can be useful to temporarily disable it during testing.
3. Finally, if all else fails, you can see exactly what the SSH server is doing by running it in debug mode on a non-standard port:
/usr/sbin/sshd -d -p 2222
Then, on the client, connect and watch the server output:
ssh -vv -p 2222 [Server IP]
Note the -vv option to provide verbose client output. This alone can sometimes help debug connection issues (and try -vvv for even more output).