6f9ad440-9d60-41fd-9a34-dfecc2cc89b5 the problem is definitely the part where the request is trying to authenticate, given the error returned and the fact that there's no audit trail. Have you tried re-creating the requirements? Roles, Integration Record, etc.
Without other details like the request itself, I can't suggest anything besides reviewing again the Setup and Prerequisite (page 3 - 6) part of SuiteTalk REST Web Services guide. Also it might be a good thing to contact support, besides, this feature is still BETA. Might be a defect?
Question. Are you following the SuiteAnswer article here:
Note, if you are following this article, make sure you download the desktop POSTMAN app version as the chrome plugin cannot be setup to work properly with NetSuite.
My suggestion is to try it first with POSTMAN.
Now, when you go to the Login Audit Trail to check logs ... make sure that you expose 'details' field in as a SS result column as it will tell you what's wrong with your request.
If you are trying to create your own authentication header via the application you are developing yourself. Make sure you generate the hash correctly. This is the most important part. You can get more info. here:
Again, my recommendation, start with POSTMAN.