No puedo conectar mediante ssh a servidor VPS

¿Has probado con algún otro servidor ssh?. Si consigues conectar con otro el problema no sería tuyo. Puede ser que ese servidor no esté bien instalado o configurado.
También podría ser que tengan los puertos cerrados (cosa rara) o que algún firewall este bloqueándote, ya sean en tu equipo en el propio servidor.
Intenta probar lo que te he dicho para descartar de donde puede venir el problema.

No tengo otro servidor ssh. Si me puedes recomendar uno lo instalo en otro equipo.
Gracias

A ver, vamos por pasos je je. ¿Es esto lo que tienes?
1. Tu ordenador (cliente de ssh).
2. Segundo ordenador (servidor de ssh).
- ¿Están en la misma red o la conexión se realiza por internet?.
- ¿El servidor pertenece a una empresa que te da algún servicio?.
- ¿Qué sistema operativo usas?.

Bueno trataré de ser claro.
Contrate un vps, osea un servidor privado. (vps=servidor dedicado chiquito), este servidor vps tiene supuestamente fedora core 4.
Yo intento conectarme a el desde mi pc con XP, mediante ssh, ya que el acceso ftp, que si logre establecer no me permite establecer una conexión root con el servidor.
El problema es que no logro conectarme a el servidor vía SSH, por tanto no puedo tener control total del servidor, esto lo necesito porque voy a instalar una aplicación web java y necesito acceso a tomcat, sdk y sql.
En mi ordenador con xp intente usar:
- putty para acceder al servidor fedora (contratado a dattatec)y me salió el siguiente error: "NetWork Error: Connection timed out"
-Luego intente con FireZilla y me dio el siguiente error:
Estado:    Conectando a ****.****.****.****...
Respuesta:    fzSftp started
Orden:    open "root@****.****.****.****"22
Error: Conexión superó el tiempo de espera
Error: No se pudo conectar al servidor
Lo que si puedo es conectarme vía FTP. Pero esto no me permite hacer nada.
Gracias, Pablo.

Vamos a ir descartando cosas:
- La conexión entre las 2 máquinas funciona. En caso contrario no podrías conectar por ftp.
- Los programas clientes usados también funciona, puesto que el resultado es el mismo.
Preguntas:
- ¿Tienes algún firewall en tu windows xp activado?. En caso afirmativo, descativalo y prueba de nuevo. Creo recordar que traía uno por defecto.
- ¿Dattatec te ha activado tu usuario para poder acceder vía ssh?.
- ¿Puede ser que el usuario no sea root sino otro que te hayan proporcionado?... Esto no lo creo, porque sino el error sería distinto.

El FireWall de windows esta desactivado.
Los datos que me envió dattatec respecto del usuario ssh son estos:
---------------------------------------------------
** Acceso SSH:
IP PRINCIPAL: 200.58.***.***
SSH:
user: root
pass: ******
Copia de lo que me mandaro, solo cambie por asteriscos la ip y el pass.(Porque las preguntas se hacen publicas)
----------------------------------------------
El servidor FTP si usa otro usuario y no root. Pero para ssh es este. Igual ya probé también conectarme a SSH con el otro usuario y paso lo mismo.
Yo creo que ni llega a hacer el control de logueo.

Pues no se que más contestarte. Si supiera la ip (solo ip) podría probar yo a ver si por lo menos conectara. Si me pide usuario y contraseña sería problema de tu conexión o pc, sino sería problemas de ellos.
Si quieres pasarme la ip puedes escribirme a israelcarrillo arroba gmail.com, sino puedes intentarlos desde cualquier otra conexión de algún amigo, trabajo, etc.
Siento no poder ayudarte en nada más.