forgotten password error. "Sorry, that key does not appear to be valid."

I am getting "Sorry, that key does not appear to be valid." for any password reset links in the email sent when going through a forgotten password procedure.

I notice that the key part of the link stays the same if I do the lost password request for the same account twice. Don't know if that should change each time or only change if it's been used.

could this be a multi-db prob? I've searched all over for someone having the same error but no joy.

Has anyone here experienced this?

(wpmu 2.8.4)