I have seen this issue with both 2k and XP clients attempting to rejoin. I was able to add them back to the domain by using root instead of admin. To do this, you must create a root smbuser using the root password from the server.
When you change the server password, you must manually change the smb 'root' user password at the command line. I am assuming you have not upgraded to samba 3.
First, look to see if you have a root smbuser. Look in /etc/smbpasswd.....you will see all your smbusers.
If root is shown, reset the root smbpasswd by typing smbpasswd at the command line (as root).
Now use root instead of admin on the XP clients.
If no root smbuser is shown, I do the following to add an smbuser:
smbpasswd -a root
then
smbpasswd -e root
You should now have a root user in /etc/smbpasswd
hope this helps you,
ryan