How should I change the permissions PRIVATEMSG for users in order them to have the access?
The normal user interface is at /messages, user/uid/messages is only meant to read messages of other users and is not a full replacement.

6.x-2.x has a feature that allows to move it around but it's relatively complex and I wouldn't necessarly recommend using.