Hi Roberto,
There is a Private Messages permission at the Root space:
Admin Console -> Spaces -> Permissions -> Space Permissions -> "Private Message"
My guess is that you have that disabled or unchecked for the users that are not seeing the option. Thanks.
-Todd