Jim,
I had this very same issue (or at least very similar) not too long ago, and the solution was a bit odd and cryptic. Are you using the legacy Unix/Linux agent or the RALUS agent? I find that my Linux backups will fail if the System Logon Account has been deleted from within the Backup Exec accounts. As soon as I recreate this account they work fine.
I would suggest that in your backup server you go into Network -> Logon Accounts (within the Backup Exec console). Make sure you see an account called "System Logon Account". If you don't, click on "System Account" on the right hand side and type in the credentials for your generic backup account. It would probably good to use an account with domain admin rights, initially, just for troubleshooting purposes, although I don't think it's necessary long term. If you already see the System Logon Account, try deleting it and recreating it, in case the credentials are no longer good. Then restart the Backup Exec services, and rerun the jobs.
In my case I would run the credential checks and they would pass. I could drill down into the selection list and see all the folders and files. But the jobs would fail very quickly with 0 bytes backed up. I tried pretty much everything until we figured this one out. I don't know why this is required, but it just works.
Let us know how that works for you. Good luck.
