@robiso22 Might fall under a "cannot change in 24hours" rule?
The only time I seen it, is if it doesn't meet the password length, it's been used before, or the complexity requires a special character. @robiso22 .. It's using the rules currently set for AD
Seen it a few times and it was because the machine fell off the domain. Perhaps look into using Apple Enterprise Connect instead? It forces the keychain to stay in Sync too. Speak to your Apple Business rep...
My guess is the cooldown. A user here can't change their password within 3 days of the last change. It gives the same complexity message, which is misleading.
I used to get this regularly, it was just caused but the machine dropping off the domain. It wouldn't show that it had dropped off the domain, but all the symptoms were there and a re-bind made the issues go away.