Hello. Some of my users can't start a conversation with any user despite all permissions set right. It even doesn't depend on user group. It may work and may don't work with different users within one user group.
If they don't get the link (I'm assuming the "start new conversation" link under the "Inbox" popup), then the system doesn't think they have permission. This is exactly what's checked:
That they are a valid user (not awaiting email confirmation or approval)
That they have permissions to start conversations
That the maximum conversation recipients is greater than 0.