You can debug your ssh connection by adding the -v switch. If the solutions below aren't helping, you at least have better search terms for google.
Make sure an entry exists for both the client and server in your dns server, or in /etc/hosts.