To answer my own question ... I engaged with Microsoft support. If you take a closer look at what the user was blocked in the Sign-In logs you will notice that the "Resource" blocked was "Windows Cloud Login".
Add "Windows Cloud Login" to the list of exceptions in the conditional access policy then it will work.
From the sign-in logs under "Basic Info":
However is you switch to Conditional Access and click on the policy that is failed you will see this:
Clearly this one's wrong.
Adding the correct resource in the CAP got it to work for me.