Can ping, can establish SSH connection in one way but not on other way

First of all, sorry for my English.

We're facing a very strange problem with SSH connection between two specific servers.

Let's say we have X1, X2 and Y servers.
Where X1 and X2 are behind the same firewall, have installed the same operating system, use same configurations for everything that's possibly related to the situation.

We don't have any rule set to allow or block only certain IPs or whatever on IPtables on server Y, but anyway... X1 and X2 servers communicate to the exterior using the same IP address.

PROBLEM: Server X1 cannot connect to server Y via SSH. It gets a response on ping, but nothing else, no other service on any other port succeeds to connect.

X2 or any other server succeeds to connect to X1 and X1 succeeds to connect to any other server except Y1.

[root@X1]# ssh -v root@Y1
OpenSSH_4.3p2, OpenSSL 0.9.8e-fips-rhel5 01 Jul 2008
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: Applying options for *
debug1: Connecting to Y1 [Y1] port 22.
** It stalls here **

We've restarted both servers and firewalls.

We've done a test on trying to connect X1 to Y using different port without configuring that port and instead of getting stalled, we get connection refused.
If we configure Y1 SSH daemon to accept connections on that port and do the same test again... it stalls using that newly configured port.