if flushing the token cache does not work then I would have to believe that something is wrong on your network with replication of the information between domain controllers.

Is this an NT4 Domain or an Active Directory Domain? 2000, 2003, or 2008 ?
What version of KiXtart are you using?