We had a similar issue before and the reason was because we had a conditional access policy.
So make sure that your Conditional Access policy exclude multi-factor authentication requirements for your solution.
Also, Have you assigned the Virtual Machine User Login role-based access control (RBAC) permission to the VM or resource group for each user? Doublecheck your RBAC settings. Make sure that you have the right permissions. Virtual Machine Administrator Login / Virtual Machine User Login.
Please note that VM sign-ins don't support per-user enabled or enforced Azure AD Multi-Factor Authentication. If you try to sign in with multi-factor authentication on a VM, you won't be able to sign in and will receive an error message.