To create new queries, or even to run existing ones, users must have access rights to the record components used in the queries. Once you have built your query trees, you must grant users access to them. You can grant and restrict access to entire query trees or portions of them through the Permission List Access Groups page (PeopleTools, Security, Permission & Roles, Permission Lists, Query, Access Group Permissions)..
Once you have built a query tree, you must give users access to one or more of its access groups. They can then generate queries on any tables in the access groups that are accessible to them.