Environment: Zimbra 8.0.4 Enterprise (using VMWare image, Ubuntu-based) and Exchange 2010

GAL is syncing, and can see F/B info of Exchange users in Zimbra, but Zimbra's not able to push stuff back to the Exchange server.

Here's what I get in the logs when I try to push my schedule to Exchange:

2013-12-13 11:34:16,650 INFO [qtp719953478-451:https://10.1.11.254:7071/service/adm...eeBusyRequest] [name=admin@mydomain.com;mid=2;ip=10.1.11.130;ua=Zi mbraWebClient - GC31 (Win);] misc - delegated access: doc=PushFreeBusy, authenticated account=admin@mydomain.com, target account=dgreer@mydomain.com
2013-12-13 11:34:16,652 INFO [qtp719953478-451:https://10.1.11.254:7071/service/adm...eeBusyRequest] [name=admin@mydomain.com;mid=2;ip=10.1.11.130;ua=Zi mbraWebClient - GC31 (Win);] soap - PushFreeBusyRequest elapsed=2
2013-12-13 11:34:16,663 ERROR [EXCHANGE2010 Free/Busy Sync Queue] [] fb - Could not find the folder in Exchange : PUBLICFOLDERSROOT
2013-12-13 11:34:16,663 ERROR [EXCHANGE2010 Free/Busy Sync Queue] [] fb - Could not find the public root folder on exchange

My suspicion is that the problem lies on Exchange, but I cannot find anything about this sort of problem on any Google search.

Any help would be appreciated. I'm hoping to fix this so we can get started with "The Big Move (TM)" away from Exchange (that can't happen soon enough for me!).

Thanks!