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.