As silly as some of these seem, I've seen them all apply at one point or another.
- Are you using the correct key?
- Have you ordered your flags correctly?
- Is your username correct?
- Have you confirmed you're trying to connect to the right box?
* do you need to have a VPN turned on?
* is your routing correct?
* does the fingerprint match?
- Is sshd running?
- Is the firewall open?
- Are the logs showing any connections?