There has been a very elusive bug around in the PostgreSQL client since 8.0 (at least) on win32. In some cases (until now unidentified) password authentication in psql stopped working, and just errored out with a message indicating the wrong password was used. And nobody has found the cause...
... until now, that is. Seems Robert Kinberg finally nailed it. At least, I firmly beleive that the bug he did identify is the one responsible for most of these reports.
Turns out that if you have a directory called \dev on the same drive you run psql from (normally c:, but that can differ), psql will attempt to use a file called /dev/tty. On Unix, this is common behaviour - we want to be sure we read the password from a tty. On windows, it just breaks - the first time, we will write the prompt into the file, and on later runs we will read back the prompt and use it as a password.
The fix is simple, just two lines changed and then two added #ifdefs. The fix is scheduled to go into 8.1.4 and 8.0.8. It's not actually approved and committed yet, but I see no reason why it won't be :-)
If you're having this problem today, check for dev directories in your root, and remove/rename/removepermissions that directory, and things should be back to normal.
So, big thanks to Robert for identifying this and suggesting the fix!