Symptoms
Running the Registration Wizard after updating to Update 3:
We see on the 4th step "SharePoint Service Broker" a "Thread 1: Remote Server returned an error: 404 Not Found" error occurs.
This occurs even when user has full permissions, Global Admin of SP Tenant, Site Collection Admin of App Catalog, have double checked the trust link sent in the email, and that all steps were done in proper order.
Diagnosis
This was discovered to be a bug
Solution
The issue was fixed by Ops and the fix will be included in a cumulative update that is being deployed.