Active Directory Exception message: Problem gaining access

A problem occurred while trying to use your mailbox. Please contact technical support for your organization  
 
Request  
URL: https://server:443/owa/lang.owa  
User host address: xx.xx.xx.xx  
 
Exception Exception type: Microsoft.Exchange.Data.Storage.StoragePermanentException  
Exception message: There was a problem gaining access Active Directory.  
 
Call stack  
 
Microsoft.Exchange.Data.Storage.ExchangePrincipal.Save()  
Microsoft.Exchange.Clients.Owa.Core.RequestDispatcher.DispatchLanguagePostLocally (OwaContext owaContext, OwaIdentity logon Identity, CultureInfo culture, String timeZoneKeyName, Boolean isOptimized)  
Microsoft.Exchange.Clients.Owa.Core.RequestDispatcher.DispatchLanguagePostRequest (OwaContext owaContext)  
Microsoft.Exchange.Clients.Owa.Core.RequestDispatcher.PrepareRequestWithoutSession (OwaContext owaContext, UserContextCookie userContextCookie)  
Microsoft.Exchange.Clients.Owa.Core.RequestDispatcher.InternalDispatchRequest (OwaContext owaContext)  
Microsoft.Exchange.Clients.Owa.Core.RequestDispatcher.DispatchRequest (OwaContext owaContext)  
System.Web.HttpApplication.SyncEventExecutionStep.System.Web.HttpApplication.IExecutionStep.Execute () 
System.Web.HttpApplication.ExecuteStep (IExecutionStep step, Boolean& completedSynchronously)  
 
Inner Exception Exception type: Microsoft.Exchange.Data.Directory.ADOperationException  
Exception message: Active Directory operation failed on server-DC1.domain.com. This error is not retriable. Additional information: Insufficient access rights to perform the operation. Active directory response: 00002098: SecErr: DSID-03150A45, problem 4003 (INSUFF_ACCESS_RIGHTS), data zero  
   
This is strange as some users cannot access OWA, but others can.  The NT AuthoritySelf and domainexchange domain servers have full access to the mailbox.