This will happen if there is more than one mail server with a public folder data base and you do not replicate a new public folder to all public folder databases. When you create a new public folder it is only created on the mail server on which your mailbox resides and is not automatically replicated to the rest of your mail servers. Your users may all be in the same group, but not on the same mail servers.
Make sure all mail stores are pointing to the same public folder store on each mail server and that all public folder stores are replicating to each other. You can use PFDAVAdmin to bulk add replicas easily. Install on your local computer, not the Exchange server. It does not work on Windows 7 at this time.