Hi @Shannon B , sorry for the delay in getting you an answer. This is currently being reported as a bug and we have a patch has been released. However, some users like yourself are still experiencing the issue.
The current proposed workaround is to go into Azure Portal and click "Enable" under the Authentication methods menu manually for each user. But as you mentioned you have thousands of users, so this is impossible.
Same issue here: https://stackoverflow.microsoft.com/questions/304250
I'm sorry that this isn't the answer you're looking for, but we're actively working on a fix. I'll share updates with you as I receive them. Please let me know if you have any questions in the meantime.
If this answer helped you please mark "Accept Answer" so other users can reference it.
Thank you,
James