I had the same problem. What it was is that the BDCs did not get a fully replicated SAM from the PDC. Change something small in there USERID save it. Then change it back and save it again. Have the user login and logout see if this works. If not try a manual sync. Usaually this worked. Good Luck.