permissions are a difficult task for the Moodle administrator. What you have to think as admin is: can this user do in the front end what he tries to do with the web service. if he can't then the user doesn't have the right capability, so it will not work for the web service too.
What web service function are you using by the way? To see user profiles try to use the function that return course participants. Most of the time users are not allowed to see any user profiles on system context, they are just allowed to see the participant profiles of the course where they are enrolled.