Exchange 2013 SP1 Installer fails on "Set the default Accepted domain from the default recipient policy"

So I had to do an update to Exchange 2013 SP1 and ran into this error. This one has been around for awhile and seems to rear it's ugly head every once in a while. So I thought I'd write a quick blog about dealing with it.

When you run the setup.exe /preparead you get some ugly output like below:

If you run the Get-EmailAddressPolicy command you don't see anything abnormal but if you run it with the -IncludeMailboxSettingsOnlyPolicy you'll see an old mailbox settings policy.
Cool but if I try to delete it, I can't :(
So we fire up our old friend ADSIEDIT and browse to the object under Configuration>Services>Microsoft Exchange> Your ORG Name>Recipient Policies
Delete the old policy and when you rerun setup.exe /preparead you get a good clean run!
Now if you look in ADSIEDIT you'll have a new Default Policy.
And now get-emailaddresspolicy returns:
The moral of the story here is that when you do your upgrade don't forget to remove any old hangers on from the old Exchange builds! Mailbox Settings in email address policies are no longer used and can cause issues of left hanging around!

......And if you're keeping track here's the last part of the domain preparation: