"Active Directory operation failed... the object already exists" when installing Exchange 2013 CU1

You may get the following error when installing Exchange 2013 RTM Cumulative Update 1 (CU1):

"Folder Hierarchies" object already exists.

This error may occur during Step 1, Organization Preparation, in CU1 setup.  Chances are it will only happen in production, not your test lab, as explained later.

If you run Setup.com from the CMD line, you will find that you can successfully extend the schema using the following command:

setup.com /PrepareSchema /IAcceptExchangeServerLicenseTerms

But when you try to prepare AD using the following command you get get the following error:

C:\2013CU1>setup.com /PrepareAD /IAcceptExchangeServerLicenseTerms
Welcome to Microsoft Exchange Server 2013 Cumulative Update 1 Unattended Setup
Copying Files...
File copy complete. Setup will now collect additional information needed for installation.
Performing Microsoft Exchange Server Prerequisite Check
    Prerequisite Analysis                                                         COMPLETED
Configuring Microsoft Exchange Server
    Organization Preparation                                                      FAILED
     The following error was generated when "$error.Clear();
        install-AdministrativeGroup -DomainController $RoleDomainController
" was run: "Active Directory operation failed on dc1.contoso.com. The object 'CN=Folder Hierarch
ies,CN=Exchange Administrative Group (FYDIBOHF23SPDLT),CN=Administrative Groups,CN=contoso,CN=Mi
crosoft Exchange,CN=Services,CN=Configuration,DC=contoso,DC=com' already exists.".

The Exchange Server setup operation didn't complete. More details can be found in ExchangeSetup.log
located in the <SystemDrive>:\ExchangeSetupLogs folder.
C:\2013CU1>

Unfortunately, the C:\ExchangeSetupLogs\ExchangeSetupLog.log file doesn't offer any other details on why the operation fails.

This happens when the Public Folder tree object has been manually deleted from Active Directory using a tool such as ADSI Edit. In some organizations it becomes impossible to remove Public Folders properly from a legacy Exchange org and admins resort to using brute force to remove them.  However, there are lingering attributes in AD that are still pointing to the deleted PFTree, which causes CU1 setup to fail.

It is important to note that this is not a CU1 setup problem, it's a problem with the Exchange topology caused by hacking out the PFTree manually.  If you still have a legacy Exchange 2007 or 2010 server you will get the same error message above if you try to create a new Public Folder database.

The workaround is to manually create a new msExchPFTree object in the Folder Hierarchy and set the msExchPFTreeType value to 1.  Here's how to do that:

• Run ADSIEdit.msc on a domain server with the AD Directory Services Tools (RSAT-ADDS) installed.  Your Exchange 2013 server should do fine.
• Expand the following path:
• • Configuration [<domainController>.contoso.com]
  • CN=Configuration,DC=contoso,DC=com
  • CN=Services
  • CN=Microsoft Exchange
  • CN=<OrganizationName>
  • CN=Administrative Groups
  • CN=Exchange Administrative Group (FYDIBOHF23SPDLT)
  • CN=Folder Hierarchies
• Right-click Folder Hierarchies and select New > Object.

• Select the msExchPFTree class object and click Next.

• Enter any value for the cn (Common Name) value, such as PF.
• Right-click the newly created msExchPFTree object and select Properties.
• On the Attribute Editor tab, click msExchPFTreeType, and then click Edit.
• In the Value box type 1, and then click OK two times.

• Exit the ADSI Edit tool.

Wait for AD replication to complete and you should be able to complete setup of CU1 successfully.  You will need to retain the msExchPFTree object in AD for subsequent CU installations.  If you delete it, you'll run into the same problem later.