The user or administrator has not consented to use the application with ID '<APPID>'

Question

We started having this problem shortly after we started using DYN365O Update 3. Our code worked for a while then one day in mid-January stopped working. We have a ticket into Microsoft but was hoping someone has found a workaround. The following error happens when our code tries to connect:

Response Code (1004) {"error":"AADSTS65001: The user or administrator has not consented to use the application with ID ''. Send an interactive authorization request for this user and resource.\r\nTrace ID: d1775f71-ac60-4d12-ace5-39b52452a5c7\r\nCorrelation ID: 38e3b5c6-52c2-4ea9-9ad1-67230e246b40\r\nTimestamp: 2017-01-29 21:42:43Z"}

I was able to use the code here (https://github.com/Microsoft/Dynamics-AX-Integration) to recreate the problem. Here is the relevant section:

    string aadTenant = ClientConfiguration.Default.ActiveDirectoryTenant;
    string aadClientAppId = ClientConfiguration.Default.ActiveDirectoryClientAppId;
    string aadResource = ClientConfiguration.Default.ActiveDirectoryResource;

    AuthenticationContext authenticationContext = new AuthenticationContext(aadTenant);

    // OAuth through username and password.
    string username = ClientConfiguration.Default.UserName;
    string password = ClientConfiguration.Default.Password;

    // Get token object
    var userCredential = new UserPasswordCredential(username, password);
    AuthenticationResult authenticationResult = authenticationContext.AcquireTokenAsync(
    aadResource,
    aadClientAppId,
    userCredential).Result;

1. When pointing to our Update 2 (August Update) DYN365O instance everything works perfectly.
2. Changing the URI to point to Update3 we begin to see these errors.

I have searched the internet and I have done everything suggested including:

1. Setting oauth2AllowImplicitFlow = true in the manifest for the Azure App.
2. Under permissions for the APP in AAD I have used the Grant Permissions to "grant permissions for all accounts in the directory".
3. Altering the call to AcquireTokenAsync to include "prompt=admin_consent". I am presented with the prompt screen but even after entering the AAD admin userid/password I get the same error.
4. Tried other users for 3.
5. Verified that the user in DYN365O (under System Administration >> Users) is identical in both our Update2 and Update3 instances and is a System Administrator.