One of our customers complained that non-admin users where unable to send private messages.
Anyone (but admin) trying to message another user got a 403 Forbidden error.
This turned out to be caused by the min_trust_to_create_topic setting being set to TL 4. Setting it to a lower trust level solved the issue.
Given how PM’s are implemented, it makes sense. But it seems to me that this wasn’t exactly meant to work this way 
The only thing that still puzzles me is that no one seems to have had an issue with this before.