The privatemsg module has a form that users submit to send a message to another user. In the submit callback for that form the message sending code is wrapped in exception handling code that displays this error message.
The submit callback does not have an awful lot of functinality that might generate an exception, and it is not possible to be definitive about the cause without inspecting your wn installation, since it is likely to differ between different installations. However, two strong candidates present themself:
1. A database issue - this module has to performa INSERTs and UPDATEs in order to "send" the message. If you have an issue such as no space on the disk to write more data or some kind of data integrity problem that could result in an exception being raised. However, we would expect you to see many more symptoms if this the cause.
2. Another module - this function _privatemsg_send($message) gives other modules the opportunity to alter the $message variable. It is highly likely that you have a custom module, or posibly a contrib module, with a function called YOURMODULE_privatemsg_message_presave_alter(&$message), which contains some code that is causing an exception to be generated.
Do check for possible database problems and inspect web and database log files for any unexpected entries. But also do a recursive search on your sites/all/modules folder for "_privatemsg_message_presave_alter" and if you get a hit look for any code that might raise an exception and make it more robust.
If you still can't track it down it is time to get serious and use the debugging functinality of an IDE. Set a breakpoint at the top of privatemsg_new_submit(), execute your code and then step through the function to see where exactly the exception is being thrown.