Any weird characters in your password?
Not even necessarily 'weird' in terms of being whitespace or anything, difference between the terminal and remote character sequences could be giving you grief?
I've seen it happen before when we had a password that worked when copy/pasted but not when typed, was also MySQL, in that case over ssh in OSX terminal.
Options in PuTTY or whatever client you're using might allow you to find a way around it, but if you're after a quick fix a test of a plain alphanumeric ASCII password is probably a good way to start.
