Avamar: Exchange Backup fails "avtar Error <5187>: Path "<machine_name>_00000000<disk>:" not found in backup (errorcode 'not sure')"

Backup is failing because of error in avtar:
 

<work-order-number->#0 (debug enabled)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2016/07/18-21:07:21.52200 [avtar]  ERROR PRIVILEGE SeSecurityPrivilege NOT HELD BY PROCESS
2016-07-18 16:07:21 avtar Warning <6970>: Current user (<AvamarBackupUser_account>) could not enable SE_SECURITY_NAME privilege.  All ACLs cannot be backed up
.
.
avtar Error <5187>: Path "<machine_name>_00000000\<disk>:" not found in backup (errorcode 'not sure').

"SeSecurityPrivilege" is missing for the "AvamarBackupUser" account.

1. Logon to the Exchange server.
2. Launch a command prompt as the Windows  Administrator  user
3. Issue the following command:
gpresult /USER  AvamarBackupUser  /V 

Make sure that the groups below are listed:
- Backup files and directories
- Manage auditing and Security log

If any of them is missing - proceed with the steps below:

1. On the Exchange server, run secpol.msc 
2. Expand "Computer Configuration"-->"Windows Settings"-->"Security Settings"-->"Local Policies"-->"User Rights assignment"
3. Double click on policies "Back up files and directories" and "Manage auditing and security logs" respectively and explicitly add "AvamarBackupUser" using the "Add user or group" option.
4. Run gpupdate /force
5. Important: Re-run  gpresults  to confirm that missing rights are displayed this time; restart the  avagent  services and re-try a backup.