If you are getting MAPI and UMR errors in the event log, there probably is a permissions issue. However, those errors don't reflect the SA problem; they reflect a different permissions issue.
Are you getting any errors/warnings from the AvDsGlobalCatalog or AvDSAD in the event log?
The SA problem may or may not be a permissions issue. You could try setting all of the AvSaDbConn traces, reproducing the problem and posting the AvCsMgr file here. The traces may or may not lead us to the problem, but it's a start.