I would first check to see if the admin has checked the “Allow other users to send me personal messages” setting in their messaging preferences (under /my/preferences/notifications).
Then I would see if the min trust to send messages site setting might be set in such a way that it is preventing the user from sending a message. If it is, you can either lower it (and potentially risk users getting spam), or you can take a look at the solution that was added here: Allow TL0 to write messages to staff group, not to other members or non staff?