Failed DCPROMO caused by AD Recycle bin on the first domain controller of a new tree domain

We are attempting to add a new (Server 2016) DC at a new AD site.  The procedure is as we have used successfully in the past:

1. Join the head office domain (this works fine) - let's call it "headoffice.company"
2. Promote the machine to be a new DC in a tree domain ("store02.company")

This is where we get the errors as follows. From the Directory Service log, ID 2140:

While processing of an Active Directory Domain Services replication request, the Active Directory Domain Services attempted to modify the list of enabled optional features for the forest.  The Active Directory Domain Services is currently enabling or disabling one or more optional features.  Therefore, modifications to the list of enabled optional features for the forest are not being accepted at this time, so the replication request failed.  The Active Directory Domain Services will temporarily discontinue this replication request.  The replication request will be attempted again later. Request Details: Object being modified: CN=BootMachine,O=Boot Attribute being modified: msDS-EnabledFeature Value being modified: 766ddcd8-acd0-445e-f3b9-a7f9b6744f2a Optional feature: Recycle Bin Feature

Event ID 1173:

Internal event: Active Directory Domain Services has encountered the following exception and associated parameters.
 
Exception:
e0010002
Parameter:
20d9
 
Additional Data
Error value:
8451
Internal ID:
11d0700

Event ID 1168:

Internal error: An Active Directory Domain Services error has occurred.
 
Additional Data
Error value (decimal):
-1073741823
Error value (hex):
c0000001
Internal ID:
30017ac

I have found this article which appears to show the same problem, but there's no solution as yet: Failed DCPROMO - First Domain Controller of a new Child Domain

The Forest Functional Level is Server 2008 R2.  We have tried different domain functional levels for the new DC to no avail.

It looks like it's just a problem with the AD Recycle Bin.  How can we overcome this error and promote the DC?