We had the same "error5(Access is Denied)" message. I discovered the "logon as" account had lost its rights to the folder the backups were going to. I granted full rights and then the job executed with no errors.

So make sure that your SQL account has the rights to write the backup, whether it be local or a remote share.