xdmpc won't authenticate with nis

I have a small group of linux servers. All are running RedHat ES 4.0.
In order to reduce administration, I set up one as an NIS server. All
of the client machines are bound to the server and can display all of
the shared maps.
These servers all have 2 NICs. Users telnet or ssh using the frontside
network that connects to the company network. All NIS binding, NFS
mounts and interprocess communication is through a backside network that
is used by only these systems.
The problem comes for the users who want to connect using xdmpc. On any
of the client machines, you can connect with telnet or ssh and NIS
authentication works. On the client machines, attempting to connect via
xdmpc you get the greeter but it fails to authenticate. The system log
shows the following messages after attempting this method.

clyde gdm(pam_unix)[5869]: check pass; user unknown
clyde gdm(pam_unix)[5869]: authentication failure; logname= uid=0 euid=0
tty=host.company.com:1 ruser= rhost=host.company.com
clyde pam_tally[5869]: pam_tally: pam_get_uid; no such user joe
clyde gdm-binary[5869]: Couldn't authenticate user

Any user can authenticate on the NIS server either locally or remotely
but not on the clients. When I removed the restriction against it, root
could log in remotely using xdmcp.

Has anyone else ever seen this problem?