Powershell – Deleted GAL in EMC and ADSIEDIT now Error

I attempted to delete a Global Address List via Exchange Management Console and ADSIEDIT as I made a typo during the creation.

Now when I try to create a new GAL, i get the following error

[PS] C:\Windows\system32>New-GlobalAddressList -Name "Tenant00001 – GAL" -ConditionalCustomAttribute1 "Tenant00001" -Inc
ludedRecipients MailboxUsers -RecipientContainer "********dc.com/HostedExchange"

WARNING: One or more global address lists were missing from the Active Directory attribute. This is likely caused by
using legacy Exchange management tools to create global address lists.
An Active Directory Constraint Violation error occurred on ***MasterDC.*******dc.com. Additional information: The
name reference is invalid.
This may be caused by replication latency between Active Directory domain controllers.
Active directory response: 000020B5: AtrErr: DSID-0315286E, #1:
0: 000020B5: DSID-0315286E, problem 1005 (CONSTRAINT_ATT_TYPE), data 0, Att 907ff (globalAddressList2)
+ CategoryInfo : NotSpecified: (:) [New-GlobalAddressList], ADConstraintViolationException
+ FullyQualifiedErrorId : [Server=C********R01,RequestId=e066151b-e695-494e-b238-f1b0f141c708,TimeStamp=15/12/20
14 17:21:56] [FailureCategory=Cmdlet-ADConstraintViolationException] 62CA54FF,Microsoft.Exchange.Management.System
ConfigurationTasks.NewGlobalAddressList
+ PSComputerName : **asvr01.*******dc.com

[PS] C:\Windows\system32>

In ADSIEDIT I deleted (right click > delete) the specific GAL in config > Services > MS Exch > Address List Container > All Global Address Lists.

The get-gloabaladdresslist powershell cmdlet confirms that the GAL is deleted.

DC is running 2008R2
Domain functional level is also 2008 R2
Exchange is 2013

Thanks