First thing, make sure you have the following update deployed:
https://support.microsoft.com/en-us/kb/3045711
Then, do you have this message only on the password change page? Or do you have it also for the regular login page?
What format do you type? DOMAIN\USER or USER@DOMAIN? Or it doesn't matter?
Note: Posts are provided “AS IS” without warranty of any kind, either expressed or implied, including but not limited to the implied warranties of merchantability and/or fitness for a particular purpose.