Did your update (disabling the complexity rules) propagated to AD users?