Win 98 unable to login to NT Domain

We are a small NT shop, and currently if I create a new user account I am unable to login to the Domain from a 98 client. I recieve the following message THE USERNAME CAN NOT BE FOUND. I able to login if I am on a 4.0 workstation. This only is occuring on newly created users. Previously created accounts can login from 98 clients. The PDC and BDC are synced up and a trace of the login shows that they are contacting the PDC and BDC. COuld the SAM be corrupted? I do have a backup but I would liketo know if anyone has had this problem. Microsofts site was no help. Thanks