You need to figure out whether the problem is with sshd or whether its something else, like a firewall. Bear in mind that ssh should allow you to get a login prompt with no configuration at all. If you just install it and its running, you should get a login prompt when you ssh to the box just like with telnet.
So, question 1 is whether you can get this login prompt if you ssh to the box and don't have anything set up.
One way you should be able to tell if its a network or ssh issue is to ssh to the box from itself - e.g. log onto myserver and type "ssh myserver". This will often connect when a firewall is blocking connections from other sources.
Two other things to try :
1. When you do an ssh, use the -vvv flag (e.g. ssh -vvv myserver). You can post the output here if its not clear.
2. Look in /var/log/messages on the server you are connecting to. If something is refusing a connection, it will often give a clue why in this file (could be another similar file).