Are there any special characters in that UPN?
In Azure AD a user is normally authenticated by the UPN attribute and in the error message it's showing those weird special characters and not the name that you are querying.
Here is the list of allowed and not-allowed special characters.
If this is the problem, there is an open feature request for this issue. https://feedback.azure.com/forums/169401-azure-active-directory/suggestions/16849114-aad-usernames-need-to-support-all-character-sets
Right now the workaround is to rename the UPN.