401 Unauthorized - "Error creating public key from user certificate" (code -7) on sandbox

Developer Discussion
1

Getting this error when calling POST /v1/transactions on sandbox:

{ "message": "Unauthorized: Error creating public key from user certificate", "code": -7 }
Setup:

Can anyone help why this is happening? Nothing changed on our end.