On a RHEL system with Samba/Winbind + external AD, some users are having login issues

Issue

• One of my RHEL systems which is authenticating against an AD (using Samba+Winbind) is presenting the following issue:

user@host's password:
Creating directory '/home/user'.
Creating directory '/home/user/.mozilla'.
Creating directory '/home/user/.mozilla/plugins'.
Creating directory '/home/user/.mozilla/extensions'.
Last login: Mon Sep 30 17:34:30 2013 from w.x.y.z
id: cannot find name for user ID 10000
id: cannot find name for group ID 10000
id: cannot find name for user ID 10000
[I have no name!@host ~]$

• This happens at random with some users. But if Samba and Winbind are stopped, their databases in /var/lib/samba deleted, and started again, then the problem is inverted: the users which worked before now don't, and viceversa for the non-working ones.
• This exact same config is running on other servers, with the exact same package versions, with no issues.