Denda,
You can create the the following logging directories on one of the failing clients:
netbackup/logs/bpcd
netbackup/logs/bpfilter
netbackup/logs/bpbkar
Legacy encryption logs to the bpfilter logging directory.
With those directories created bump up the client side logging, if a UNIX machine, go to the bp.conf and add 'VERBOSE = 5', if it's a Windows client, bring up the Backup Archive and Restore (BAR GUI) tool from the start menu, and then go to File -> NetBackup client properties -> troubleshooting tab. There set the general logging level at 2 and the verbose at 5. Click okay, and close the BAR GUI.
Now re-initiate the job.
Investigate the aforementioned logs.
My first suspicion is that an encryption key file may not configured on the client, or the encryption package hasn't been installed on the client.
-Sean