What version of KiXtart?
What client versions?
Have you looked in the event viwer for the clients to see what if any errors are being generated.
How many Domain Controllers?
Are all Domain Controllers replicating correctly.
Check and Double check replication
Is it one or two clients or all clients having issues?
How many clients overall on the system?
What are the link speeds of the network?
Have you check to make sure no one has modified the rights and that the logon is setup in the admin tools.