Not sure if it is a plugin I've installed or not, but somehow I've borked my Private Messaging so that users whose usercp permissions allow private messages cannot receive private messages, from admins or whomever.
The following errors occurred when this message was submitted:
USER has chosen not to receive private messages or may not be allowed to receive private messages. Therefore you may not send your message to him/her.