1. There's a character limit. If you're just playing for the first time, you might need to know this. It's 8, I believe - Is your password more than 8 letters long?
2. Is there any complex characters like ^ or something? I /think/ there might be issues with that, I forget though.
3. Passwords are caps sensitive. Make sure you've done all correctly.
4. It might take a small amount of time for the new password to be changed and stuff, but I doubt this is the issue. Although, I thought it might be worthy of mention.
Are you a new member, or just logging on again?
EDIT: Enoki corrected me - The character limit is, in fact, 16. My apologies. ^^