It might be the password input not properly cleaned up, think of the leading or trailing spaces on password, these could confuse the user, specially when he miss copy/past the password from the email message.

Tell them to use a password manager and call you back if the problem persists.

Are you sure it's not the system? I use a password manager, and often have a problem with sites forgetting my password (examples: Wordpress.com, Mojang.com, Ebates.com, Steam, my local credit union). I don't know what stupid method these sites are using to store passwords, but the problem has mostly gone away since I changed from "26 characters w/ special characters" to "10 characters w/ no special characters".

@BlueRaja-DannyPflughoeft I'm no Russel's chicken, so cannot be sure! However, they usually report that password was something like theirname123!!

Yeah I've definitely had websites eat some special characters silently when the pwd is set, which I only realize when I try to log in.

Some good answers here, so I won't repeat them. I'll just prod you in the direction of doing some QA on your own system. You can't intercept/reveal the user's password, so generate a test user. That way, you have absolute control over any correct/incorrect passwords submitted, and you'll be able to test your own auth system as a black box (and can test the salted hash of the password quite easily too). It should be fairly easy to reproduce the original issue and see if the same occurs under test. It might also inspire you to improve your error message UX and/or add some automated test cases.

What on Earth makes you think they will believe you when you send some technical mumbo-jumbo their way? They already believe that your system "forgets" passwords, do you think that showing them some hashes and telling them it corresponds to something will do something other than make them think you're trying to confuse them to cover your ass?

You could try cracking the password hash using a rainbowtable.

@BlueRaja-DannyPflughoeft Usually when that happens the site has decreased the maximum password length and you're unable to fully input your password. It's easy not to notice this if the new password length is still long enough to fill the password field.

@Mario Trucco use packets and look at the sent and return response if it is a website. A 404 is forbidden anything other than 200 is not ok and 302 is redirect. If the issue still is not obvious, you should keep logs of login attempts (void of data) explaining errors and issues. Search these with something like elastic search. If worse comes to worse, look directly at the password and dehash it. The salt should be available.

For completeness's sake only, you could start storing their passwords and then point to it and say "No, this is your password."

As a matter of fact there shouldn't be a 'wrong password' error message in the first place. That's an information leak to attackers that they have hit on a correct username. The message should just say 'invalid credentials' when either the username or the password is wrong, i.e. when there is no user with that username and that password. That might give you insight as to how your authentication system should actually work, and changing the message might also reduce the heat from users on this particular situation. The smart money remains on a bug in your system.

Statistics to the rescue. Do you know whether this happens statistically significantly more often with your service compared to other services? I'm not sure how one would find out the baseline rate of authentication failure for the average web login, but if you're not significantly higher than that I think that's a form of "proof".

"You can't intercept/reveal the user's password" - yeah you can. I bet your terms and conditions say something like "we store literally everything you ever do, and use it to improve our products and services", right? (I'm not saying you should, I'm saying in the extreme if you had to choose a working product and happy users and a profitable business, or 'security' perfection and unhappy users and bankruptcy...)

@TessellatingHeckler Happy users become unhappy very quickly when critical secrets of theirs are exposed due to lack of security in your system

@MarioTrucco a) why would you expose them anywhere? b) How would the users know? and c) [citation needed]. Geeks do, but where is the evidence that anyone else even cares at all?

One thing no one seems to have considered here is the possibility their account was compromised and someone else changed their password. Reset function should be used before support though.

@EJP Some sites, such as Stack Overflow, will tell you whether an email is registered if you try to register with it, although it doesn't tell you when you try to log in with it. I think it's no big difference if they also tell you whether the email is correct when you try to log in.

Perhaps an alternative is to store the hashed value of a second and subsequent failed event. If these are always the same for a given user every time it fails for them then you have a reasonable confidence that they are typing in the same thing each time and the error is deterministic.

@TessellatingHeckler: Storing hashed passwords without salt is grossly incompetent. Storing passwords is... Let's just say anyone doing that should be shot on the spot. Anyone suggesting it should be given 500 lashes and then asked if they changed their mind.

@gnasher729 don't mistake 'slavish adherence to dogma' for 'security'. Logging to a file on a controlled server for a limited time period for the purpose of debugging a genuine problem != changing the design of your password handling forever and != the sky falling on your heads. It doesn't even need to hit the disk.

@EJP - "... there shouldn't be a 'wrong password' error message ..." Telling a user who is logging in, that the "Username" they typed is not found, or that the "password" they typed doesn't match their username is a convenience to the user. It's a good thing, a necessity. Embrace it and move on. While it does expose a way for an attacker to know what usernames are valid, there is an easier way for an attacker to get this information. Usernames (of course) have to be globally unique, so an attacker can use the "create new account" page to find usernames that are "unavailable".