First Run – On one particular occasion a client of mine and I were going through the wizard, we created the TXT record in DNS, entered the authentication credentials for On-premise and Office 365. When we completed the wizard and clicked Finish, the wizard presented us with an error message that something had failed.
Second Run – We assumed that maybe there was a credential issue. We ran the Hybrid wizard once more and verified the login accounts and passwords. Clicked Finish once more and the same error message appeared as the wizard had failed.
Third Run – This time we decided to verify that the TXT record correct as this was the only part that was new or configured during the run of the wizard. My client checked his DNS providers TXT entry and it record was there and it looked correct. We then re-ran the wizard thinking that it would work. However, once again it failed.
We then decided to review the Hybrid logs for error messages found this message in the Hybrid Log file:

The error message makes it clear that the DNS record was the issue. However our DNS provider had shown the record as present, so why would we get this error? If your domain is like most, there are usually two or more DNS name servers that handle DNS queries for your domain. Maybe the record was missing from one of the servers. How to we find this?
We fired up a browser and upon checking several DNS query sites, noticed that the TXT record did not appear to have replicated. An easy on to use is the DNS Query Tool that can be used to select which DNS server to use to verify replication:

If you do not know what your DNS Server is, use this site to find your name servers:

In the case of my client, the TXT records was showing properly on one of the domain’s name servers, but was completely missing from the second server. We then decided to wait until the record had replicated. Once replicated, we attempted the hybrid wizard for the fourth time.
Fourth Run – Another failure! The Hybrid Wizard displayed a different error message now, with text similar to this in the ‘failed’ window –> “Same URI cannot be attached to different AppId on a single day”.
Solution
Sometimes you just have to wait, as Microsoft makes clearly in this KB Article. In this case, because we had 3 failed attempts, we now needed to wait for 24 hours until we could attempt another run the Hybrid Wizard once more.
So the moral of the story is, check your credentials, review the Hybrid logs, check your DNS records and make sure that is has indeed replicated to all of your name servers for your public DNS Domain. Lastly, make sure you fix any issues before your third run, or you too shall wait.