Did you log in as the users in question, or did you looked at the policies/roles in the full view of the users in the admin interface? It could be a view caching issue, clear the content view cache then. Maybe clearing the user info cache is necessary too.
I advice you to use a more recent release of eZ publish, like 3.8.5 (3.8.6 introduced some nasty e-mail bugs).
