I had this the other day when users were trying to manually change their password through alt+ctrl+del. It wasn't the complexity (although the message claimed so) its the policy that says "password must be at least 30 days old before being allowed to change". Not sure if this is a newer password they are trying to change with your problem, but this does sound similar.
Its in group policy, default policy, Windows Settings, Security, Account, Password and in there.