I think I have finally found the reasons! The Tableau server is configured to use SAML for SSO signin, and Tableau REST APIs specifically don't work with SAML!
Note: The REST API does not use SAML single-sign (SSO) authentication. To sign in, you must specify the name and password of a user who has been created on the server. The user could have a local or Active Directory account, depending on how you have configured Tableau Server. For Tableau Online, you can specify the TableauID credentials of the user. You will have the permissions of the user that you're signed in as. You cannot use a SAML account for sign in when you use the REST API. For information about the requirements for using SAML, see SAML Requirements.
So, I'll now need to create a native Tableau user and try that with the REST API. Hope that works.