They are probably already doing this - but when the user logs into Field Maps, are the logging in the exact same way as they do to ArcGIS Online or if they access the server?
For example - we have SAML/Google hosted logins. If users log into Field Maps with the text boxes instead of using the organization log in, Field Maps tends to not function correctly for the user! So in this scenario, if the user is not logged into Field Maps with the same credentials as they would for Online, that could be the problem.
Aside from Field Maps - is the user able to access the service in a browser window? You may have already tried this, but I would have the user try to login/access the map service in a browser window (probably Chrome) first to see is you have the same error! If they can't login through the browser, it will for sure not work in Field Maps. At that point, it might be a server/domain issue.
Good luck with your projects!