Use the Wiki Permissions > User Access Masks page, enter the name of a user that is having trouble, and look at the Not Set column. It should tell you all the wiki permissions that user has and where they were inherited from. This might help you find the source of the problem, if there is one.