Privilege separation user sshd does not exist woes

I have a bunch of CentOS 5.x boxes where ssh will occasionally become
non-responsive with the message "fatal: Privilege separation user sshd
does not exist". But the local user does of course exist. If I login
from the console and restart sshd, it comes back just fine.

If it provides a clue, the boxes use ldap, but are correctly
configured in nsswitch to look for local users first. I was suspicious
of nscd, but it isn't running everywhere. I don't find a RHEL bug
report that describes this problem. Anyone ever seen this? Suggestions
for troubleshooting? I'm stumped. Any suggestion would be appreciated.