Experienced this exact error message after updating our Compliance Policy Password Requirements.
MS Guidance indicated that having the user reset the password would resolve this issue, this was not the case.
Further research led me to find that the CSP's do not allow the "Special Character" option on Win10 machines.
We altered the Compliance profile password complexity to omit the Special Character requirement and all devices became complaint again w/in 24 hours.
Still looking into how we can enforce this requirement and monitor the results from our Compliance Policy.