Compose a Message and even as the board admin I get:

"The requested users to be added do not exist.
The submitted form was invalid. Try submitting again."

Reply to a user who sent you a PM or add their name and you get:

"The requested users to be added do not exist."

Tried clearing the cache on the server, cleared cache and forms and authenticated session in browser, etc. but no change
-----------------
Update
I cleared everything including cookies as well (which is painful to lose) but that seems to have fixed the problem (using Firefox 3). So phpbb3 stores something in a cookie which then causes it to spit out the errors above whenever anything is done with private messages afterwards.