So I just go a Samba 3.x setup on a CentOS 5 box, LDAP authentication,
everything is working nice. I attempted to start joining PCs to the
domain and I kept getting "user not found" messages.

Here is the deal, I racked my head for several hours before realizing
what was causing this problem. Make sure that in your ldap.conf file
you have a nss_base_passwd set to not only where the users are stored
in the LDAP database but also where the computers (users) are stored,
here are some example lines below.