The new password handling mechanism uses a server provided challenge word, that with the typed password is md5 hashed, and it is this hash what is sent to server as password.
But the challenge word is only valid for 5 minutes after generated. Because of this, the page as a "<meta http-equiv="refresh" content="300">" to force browser to refresh the page every five minutes, for users that eventually left the page open for more than that before login. This usually work, but, if the page is retrieved from the browser cache, will fail because it will retrieve the old challenge word too. Can you please check to see if this is what is happening in your case. If eventually this is the problem, I can try to add a javascript refresh function that, on new browsers, can force browser to request the new page from the server, and not from the cache.