Linux error id: cannot find name for user ID xxxxx when using Domain Authentication

We recently had a problem, after re-doing some samba configurations on RHEL 5, in which a user would log in (successfully), but then be presented with the follow errors:

id: cannot find name for user ID 10001
id: cannot find name for group ID 10000
id: cannot find name for user ID 10001

Of course, none of our domain ACLs worked for this user, either, which was a real problem. Finally, after running through the more obvious problems (communication with domain controllers: verified with wbinfo; uid and gid allocation and linking: set explicitly with wbinfo; winbind cache (cleared, both in /var/cache/samba and /var/lib/samba); date/time discrepancies; domain membership), we found the culprit: file permissions.