Server 2000 and NT4 domain permissions

On a domain with 2000 server and NT4 server running active directory and NT4 server running exchange 5.5. the 2000 server was NT4 then was upgraded. Everything seemed to work fine for few months, but later on it was noticed that new user accounts that were added after the upgrade, do not have rights to access the NT4 servers. The NT4 BDC shows the newly created accounts, but when trying to access the BDC and exchange server (member server) access is denied, or askes for a user name and password rather. On the same machine an old account works right, but a newly created account does not. Any ideas?
thanks,
David