Managed Apple ID iCloud sign-in fails on ABM/Intune iPhone

I'm actually not sure if this is an Intune or Apple Business Manager issue, as they are working together, but I figured someone here must have experience with this situation.

I'm trying to get my first iPhone up and running under Intune, via ABM. I've hit lots of obstacles on the way, but I've managed to clear most of them.

Apple Business Manager is set up and communicating with Intune. I've just registered the first iPhone: it shows up in ABM, it shows up in Intune under iPad/iOS devices, and it says it is "Corporate" owned, with the "Primary User" correctly identifying as the one I used to enroll the phone during initial setup.

I am now trying to login to iCloud, with the same username and password. My domain is already federated with ABM and all my Entra users appear in ABM as "Managed Apple Accounts", but when I try to sign in to iCloud with that account, I get the following error:

Verification Failed

You cannot sign into this device using this Apple ID. Contact your organisation's administrator for assistance.

Cool. That's me. I've contacted myself and I have no idea why I can't login to that account.

More interestingly, I googled this error, and I couldn't find any results at all with an exact match. So, if I can find the solution to this problem, I guess this will be the first useful search result?

I tried logging into iCloud.com with the same account, and I got the following error:

This Managed Apple Account needs to be set up from a device. Sign in to an iPhone, iPad, or Mac to finish setting it up.

But I *am* trying to login from an iPhone... 😭

Based on the error message, I'm really not sure if it's a problem with the Apple ID itself (some step I've failed to take in setting up the Managed Apple Account?), or in the relationship between the Apple ID and the iPhone ("You cannot sign into *this* device").

But ABM doesn't show me any other options for this Federated Entra User: the Managed Apple Account appears under the user name exactly as it should.

And since the profile for this phone is configured in Intune for User Affinity, and enrollment is User Driven, and the device already shows the user in question as the Primary User, I don't see any other options for "authorizing" a specific user to use a specific iPhone...