I was having the same trouble and found this:

http://blog.stealthpuppy.com/exchange/exchange-server-2007-and-public-folder-replicas

...not my fix, but it did seem to help some people.