Windows Authentication on restore

I am getting an error e0000383 when attempting to do a restore with BE 2010 R2. Only one account will run the restore properly without generating this error (the System Logon Account). This is a domain account with local admin rights on the media server. Even the Backup Exec Service Account will generate this error (a local account with admin rights on the media server). I have two other domain accounts that must be able to do restores - both of these have local admin rights and both are members of the local Backup Operators Group.  I have checked the Local Security Policy settings and all these accounts have 'log in as a service' and 'log in as a batch job' enabled.

Here is the job log text:

Job Log: BEX_SFC-NCIREDOD_01399.xmlJob Log for Restore 00145 

      Completed status: Failed    See error(s)
      Expand AllCollapse All

      Job Information
Job server: SFC-NCIREDOD
Job name: Restore 00145
Job started: Monday, April 04, 2011 at 4:05:55 PM
Job type: Restore
Job Log: BEX_SFC-NCIREDOD_01399.xml

      Job Operation - Restore
            Server - SFC-NCIREDOD
Failed to log on to Microsoft Windows.

Ensure that your logon credentials are correctly entered and that they meet the following minimum requirements to log on to a Windows computer:

   - The credentials used are a member of the Backup Operators group.
   - For Windows Vista/2008 and later, the credentials have the Log on as a batch job privilege.

Additional privileges may be required to access resources on the Windows computer.

 

      Job Completion Status
Job ended: Monday, April 04, 2011 at 4:05:56 PM
Completed status: Failed
Final error: 0xe0000383 - Failed to log on to Microsoft Windows.

Ensure that your logon credentials are correctly entered and that they meet the following minimum requirements to log on to a Windows computer:

   - The credentials used are a member of the Backup Operators group.
   - For Windows Vista/2008 and later, the credentials have the Log on as a batch job privilege.

Additional privileges may be required to access resources on the Windows computer.
Final error category: Security Errors

For additional information regarding this error refer to link V-79-57344-899

      Errors
      Click an error below to locate it in the job log
Restore- SFC-NCIREDODFailed to log on to Microsoft Windows.
Ensure that your logon credentials are correctly entered and that they meet the following minimum requirements to log on to a Windows computer:
   - The credentials used are a member of the Backup Operators group.
   - For Windows Vista/2008 and later, the credentials have the Log on as a batch job privilege.
Additional privileges may be required to access resources on the Windows computer.

 

I very much need to have these two domain accounts be able to do restores. As with EVERYTHING with Backup Exec, I am glad I ran through a test restore with these accounts.

Thanks for any help/ideas with this.