Transaction process correctly, but person receives an error message that transaction failed

Content

We have started receiving notifications from our teams that (intermittently) employees are submitting Core HR transactions, like Award Compensation, and the transaction processes successfully. However, even though the transaction is processing as expected, they are receiving the following error message, "User does not have privilege to execute web service or there are deployment issues with the web service."

These are transactions that the users have submitted several times and we have verified that they do have the privilege to execute the task. The tasks are processing correctly and the changes are being reflected in the employee's records - they are just getting erroneous messages which require verification.