I’ve had previous issues (with older versions of acronis backup software) where mapped drives as targets for backup jobs would occasionally fail when the software believed that the credentials for the connection were wrong. You will find that blog here.
So when I saw a falied job mentioning the credentials not being correct – I thought I had the same problem again – however in this case checking the actual error showed some more information. In this case it said “the server’s clock is not synchronised with the primary domain controller’s clock”. Checking this discovered that the two servers clocks differed by 1o minutes – with the failing server being 10 minutes fast. After adjusting the clock to match the correct PDC time found that the failing job was able to run. So perhaps the next time you job fails check the servers time before you start changing the job definition or user credentials.