Exchange 2010 Cannot add or modify Mailboxes

I am trying to run a script on Exchange 2010 as well as trying to add a new mailbox and I continue to get the dreaded, Active Directory operation failed on hobbes.rockwall.genesta.com. This error is not retriable. Additional information:
Access is denied.
Active directory response: 00000005: SecErr: DSID-03151E04, problem 4003 (INSUFF_ACCESS_RIGHTS), data 0
    + CategoryInfo          : NotSpecified: (0:Int32) [New-Mailbox], ADOperationException
    + FullyQualifiedErrorId : 1F5ED462,Microsoft.Exchange.Management.RecipientTasks.NewMailbox

I have done everything I can think of to resolve this. I am using my account with the following settings:

Member of:
Domain Admin
Domain Users
Enterprise Admins
Exchange Admins
Organization Management
Schema Admins

I have also checked and rechecked the Include inheritable permissions from this object's parent and this box DOES have a checkmark in it.

I am in a very crucial situation here. Thank you in advance.