DNS check

The first thing I would check would be DNS. This sort of flaky binding and authentication behavior is classic bad DNS.

Run the following commands on the server and on your client machines and make sure the results always match. Proper forward and reverse DNS is important for OS X Server.

nslookup <hostname of the server>
nslookup <ip of the server>
dig <hostname of the server>
dig -x <ip address of the server>
host <hostname of the server>
host <ip address of the server>
dscacheutil -q host -a name <hostname of the server>
dscacheutil -q host -a ip_address <ip address of the server>

On the server only, run this:
sudo changeip -checkhostname

It should say "Success. The names match. There is nothing to change." -- If it says anything else, DNS is broken.

- Mike