This is almost always a send as permissions issue. I would double check that the users having the problem are inheriting from parent container in AD. The check box for this is on the Security Tab of their user properties page.
If you have already, try re-running the permissions wizard.
Hope that helps,
Brad