Similarities are:
User cannot log into his account with old PW. We get the message, I let them check their software, request new PWs. Doublecheck the captach. Type the PW in a text editor an copy it to the web interface. The full program. In most cases it results in "PW or Captcha incorrect" messages. And in most cases it works again after a while but just by trying again and again. Nothing specific (believe me, I would tell you). Now, I have (at least) one guy here that cannot get into their account for 2 days! Maybe there is a second one but I haven't heard from him today. And actually I am absolutely helpless cause I don't know what to tell them.
If you're starting to get to the hair-pulling-out stage, then in order to comprehensively diagnose, you _may_ need something like UltraVNC, to effectively take control of the end-user's computer and/or see what they see on their screen and be able to watch exactly what they are doing. You'd probably get them to put their username & password into a text editor (so that you can see them, and watch them be copied/pasted), and then observe them try to login. At the server end, I'm guessing there'd be some method for a sysop to monitor the login failure reason, and communicate that reason back to the people trying to login. Hopefully this method would allow ruling out both client and server-side issues (since effectively both the client and the server are being monitored & controlled in this scenario) - e.g. mistyping the captcha, entering the wrong password, problems with throttling login attempts, etc.
It's a lot of work though, and getting UltraVNC set up and the appropriate ports forwarded through their firewall/router (and for security turned off again once you're done) can be a fairly technically involved endeavour in its own right, plus the end-user has to be comfortable with someone temporarily taking control of their system.
-- All the best, Nick.