samba PDC and user authorization problems

Hello all,

this is my initial post to usenet groups since about 2000. I hope I am
posting to the right group and that I am following all the rules I
should (...)

I need some help with one of my Samba servers. It is working as
primary domain controller. Most of users connected use win98se. They
log into the domain and the have access to the shares, and also there
are netlogon scripts running on their workstations.

Problem: Sometimes there is problem with logging in. Users want to log
in, they type login and password correctly, and the server responds
that password is invalid. They repeat the process several times, and
eventually they log in and everything is ok.

The problem was observed with Samba 3.0.22, and persists with upgraded
Samba to 3.0.24.
I switched from passdb backend to tdbsam, but it did not solve the
problem. One error I can observe in logs is :

[2007/03/14 15:15:11, 5] passdb/pdb_tdb.c:tdbsam_getsampwrid(1103)
pdb_getsampwrid (TDB): error looking up RID 513 by key RID_00000201.
Error: Record does not exist

I don't know why it exist and how to fix it? Linux and windows groups
are mapped correctly I think - but I had to do it manually (why?) with
net groupmap command.

net groupmap list gives output:

Domain Admins (S-1-5-21-3046282495-2356171298-3516334198-512) -> wheel
Domain Guests (S-1-5-21-3046282495-2356171298-3516334198-514) ->
nobody
Domain Users (S-1-5-21-3046282495-2356171298-3516334198-513) -> users

Gentoo Linux, dual P3-1000, 256mb ram, hardware raid.... if it does
matter.
Help and any ideas appreciated.

Regards,
Piotr