Access denied to Win 2000 share from NT client

Hello folks,

We have a domain with two Domain Controllers
- AAA a Windows 2000 Server (SP4)
- BBB a Windows 2003 [Terminal] Server

There are Win 2000, Win XP and Win NT clients, all being members of
the domain.
All clients can access shares on BBB.
Most clients can access shares on AAA, but none of the NT clients (SP6
or SP6a) can.

In fact,
NET USE X: \\AAA\SHARE
works, but
DIR X:
will fail afterwards (Error 5, Access denied)
Sometimes, a second
NET USE Y: \\AAA\SHARE2
will fail as well (user is asked for a password and then fails).

I suppose that it's not a rights issue (the same user can work from
another client), nor is it a trust relationship issue (the NT boxes
are members in
the domain with computer accounts and all that stuff), nor a mixed
mode issue (this should not apply to clients, should it?).

From whatever I check (e.g. netdiag), it looks as though it just has
to work.

Ideas anybody?