First ensure that your service is running (and I reccomend changing the port it runs on).
Next, ensure that the service is running.
Thirdly, ensure that any port forwarding thats needed is in action (as in you are behind a router/gateway)
Fourth, ensure that your settings are correct in the client. Generally (I think Red Hat, CentOS, and Fedora are this way) root cannot login by default, and that is good. Setup sudo and use sudo su to gain root if you must, otherwise just using sudo is a good practice.
Your client (putty, which rocks BTW), will need the hostame/ip, port, username, and then finally your password.
That should be it. I have setyup tons of systems with ssh/sudo for years now, without issue (Red Hat, CentOS, Fedora, and OpenBSD). Its probably a port forwarding issue if you ask for my one guess.