Salesforce recently changed sandbox refresh behavior and will mark users as "Frozen" on refresh. I had to "Unfreeze" the user defined as the Run As user in the Client Credentials Flow settings, and this resolved the issue.