Yesterday and today, when I first tried PM'ing a user, the message preview screen has told me that the user does not exist. (The user obviously does in fact exist.)
Logging out and then logging back in resolved the issue both yesterday and today.
Thought the issue might be related to my script-blocker, but turning that on/off and logging in & out (and starting new browser sessions) hasn't replicated the problem.