If I remember correctly, the times when users had this issue, and the actually got back to me about it working again.
The problem was that they requested several password resets from the site, over and over, without looking in their junk mail folder or correct mail. Once they actually found a mail, it wasn't the first one. I believe it's just the very first token you, the user ask for, that works. All the other ones will say it's incorrect.