Can't log in off line

I have an odd one.

I have two users sharing a laptop joined to a domain. The login's will work
fine for a while then after one uses logs off while away from the network the
other user can not log on. Only the last user can log back in. The machine
has been working offline and online fine for a number of months.

They get an error msg that their password is incorrect.

We have rebuilt the laptop and rejoined to domain.

Any help appreciated.