Private messaging doesn't work

Permalink 1 user found helpful
I have the 'I would like to receive private messages' attribute enabled, but the link to send a private message still doesn't appear in the user profile page.

Is there anything else I need to set to enable it? Maybe it has something to do with permissions?