1. Are any of your users present in more than one role? Unlike SQL Server RDBMS, denied privileges do not trump allowed privileges but are a UNION of all privileges.....like a bitwise OR.

2. When entering dimension level security, did you make sure you entered the MDX expression in the "Allowed Set"?