Domain connection becomes flaky, but why?

I just had a server in our lab disallow me from adding it as a host in Windows Load Balancing.

Suddenly, out of the blue (cause this has been working fine), when I tried to re-add the machine into the load balanced cluster, it requested credentials. I am logged in as a domain administrator which is the same procedure I've used to add the other machines into the cluster and even this machine in the past. When I supply a local machine administrator credentials, it allows me through.

When I look at the administrators group, all domain accounts display only SID's (rather than the friendly display names). When I try to add domain admins it reports that the account already exists.

The only way I could resolve this was to remove the server from the domain, reboot, and add it back onto the domain, and reboot.

After that, everything was fine and I could add the machine back into the load balancing cluster without any problems while logged on with the same account that was originally refused.

Does anyone know what caused this, and if there is a less extreme way to correct this problem?

Updates: Event logs are not very usefull as we have a application on the server that generates allot of events, and by the time I realise the problem the event log has cycled, but I have oberved some DNS related entries in the past.

We also had major issues with the time service in the past. According to Microsoft the clocks should just sync with the PDC by default. Yea, right... we had Microsoft out for about 3 days before they could resolved the issue. (Turned out we didn't have NetBios Installed) This is however resolved now, and I confirmed the time when I realised the issue, because I know this has been an issue in the past.