This has been resolved - yes we would log in with a different user on that same device and the same user could not log into another device so we were pretty sure it was not the device.
When the account was created there was a misspelling in their name and was corrected. The misspelling stayed on the .onmicrosoft account and when we tried to log in with their UPN including the misspelling in the name it worked.