we do face this problem long time before. We could not find hte root cause of the issue. Some of the users are not even login to incident/change management console, still they have all the appropriate permissions. After deleting the people records from database, and creating the new people record with the same permission, it worked fine.
Is this any thing related to user cache or people feed process???? Im not sure about this.
Make sure that the users are getting Unrestricted Access or being restricted to a certain company. You can check this by looking at their user record on the User form. Make sure they have Unrestricted Access or that they have a number in their permission list.
You can trigger a rebuild of this list by going to their people record and check/uncheck or conversely on the unrestricted access field.