Try changing it again, see if that helps. There's no reason the phone would not recognize it, unless of course you're typing the wrong one in. Try changing your password again, then reboot your phone and try again.
If the phone won't accept the current password, you're logging in with the old one - which won't work. (Don't use weird characters - # is good enough for special characters. Or a dot. Or !