Stange sshd problem... bug?

[Pedro Bezunartea Lopez]

I haven't been able to find any information about this problem, I hope
someone can help, anyway this is the setup:

Server:
- Linux Fedora Core 5
- kernel 2.6.17-1.2145_FC5smp
- openssh-server-4.3p2-4

Client not working:
- Linux Fedora Core 5
- kernel 2.6.17-1.2145_FC5smp
- openssh-clients-4.3p2-4

Client working:
- Same machine
- Windows XP
- putty 0.58

This is the log from the non working client:
$ ssh -v elk1
OpenSSH_4.3p2, OpenSSL 0.9.8a 11 Oct 2005
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: Applying options for *
debug1: Connecting to elk1 [**IP-removed**] port 22.
debug1: Connection established.
debug1: permanently_set_uid: 0/0
debug1: identity file /root/.ssh/id_rsa type -1
debug1: identity file /root/.ssh/id_dsa type 2
debug1: Remote protocol version 1.99, remote software version OpenSSH_4.3
debug1: match: OpenSSH_4.3 pat OpenSSH*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_4.3
debug1: SSH2_MSG_KEXINIT sent

And from the server:
Jul 12 03:12:13 web1 sshd[3707]: debug1: rexec start in 4 out 4 newsock 4
pipe 6 sock 7
Jul 12 03:12:13 web1 sshd[1839]: debug1: Forked child 3707.
Jul 12 03:12:13 web1 sshd[3707]: debug1: inetd sockets after dupping: 3, 3
Jul 12 03:12:13 web1 sshd[3707]: Connection from **IP-removed** port 47346
Jul 12 03:12:13 web1 sshd[3707]: debug1: Client protocol version 2.0;
client software version OpenSSH_4.3
Jul 12 03:12:13 web1 sshd[3707]: debug1: match: OpenSSH_4.3 pat OpenSSH*
Jul 12 03:12:13 web1 sshd[3707]: debug1: Enabling compatibility mode for
protocol 2.0
Jul 12 03:12:13 web1 sshd[3707]: debug1: Local version string
SSH-1.99-OpenSSH_4.3
Jul 12 03:12:13 web1 sshd[3708]: debug1: permanently_set_uid: 74/74
Jul 12 01:12:13 web1 sshd[3708]: debug1: list_hostkey_types: ssh-rsa,ssh-dss
Jul 12 01:12:13 web1 sshd[3708]: debug1: SSH2_MSG_KEXINIT sent

And it just freezes there. I've tried to set a smaller mtu, but the
problem wasn't solved. When I connect to the same server using windows XP
it works, so it has nothing to do with the hardware.

I should also say that the server is behind a firewall and that it has
been working fine with previous kernels.

Any ideas? Anything else I can try? TIA,

Pedro.