We will need more information, for example, the content of sshd_config (eg., /etc/ssh/sshd_config) file, and the state of the server IP tables ("iptables -L" ran as root or through sudo).
A couple of things that worked for me in the past:
Do you have a router between your computer and the server? Is it blocking port 22? Is your ISP blocking port 22?
Try another port by changing the Port directive in your sshd config file and restarting your sshd daemon:
Are you using TCP wrappers (e.g., what do you see in /etc/hosts.allow)? This is independent of the firewall.
As a previous user mentioned, are you trying to log as root (not recommended, but then, you need "PermitRootLogin yes")?