X apps only work after second login

My apologies if this has been addressed previously - I didn't see  
anything for it in the archives.

We're in the process of upgrading to RedHat Enterprise version 4 and  
are seeing a strange ssh problem. It ships with what they label as  
"openssh-3.9p1-8.RHEL4.4." Telnetting to port 22 on the box indicates  
SSH-1.99-OpenSSH_3.9p1.

We're using a vanilla install. The only change we've made is one  
variable in sshd_config - we've got the following variable  
uncommented: X11UseLocalhost no.

Here's what happens:

1) User ssh's into remote machine (machine.company.com) which is  
running the new version. Tries to run an X process, say xclock. User  
is told:

Error: Can't open display: machine.company.com:10.0

User keeps this session open.

2) User opens a second ssh session to the same remote machine. Runs  
xclock - it works. On this second session the client has been handed  
the same display (machine.company.com:10.0) as the first session.

3) User goes back to first session. Now xclock works in that session  
also.

4) If user logs out of second session, X stops working on first session.

We see this behavior regardless of the ssh client used (we've tested  
Linux, OSX, HP-UX). It also doesn't matter if we use X forwarding on  
the client (via -X or -Y) either.

Note that if a user doesn't have concurrent ssh sessions open, X  
never works.

Any suggestions?