Check whether the services are running with Domain Administrator Account.
Check whether the Remote Agent for Windows Servers Service is running with Local System Account.
Check whether port 10000 is open on the server.
The following document could be helpful as well.
After changing the Backup Exec "service account" using the Services applet, the error message: "A required privilege is not held by the client" is displayed after clicking the "Backup" button.
Note: If we dont receive any reply within two days , the post will be considered as "assumed answered" and will be moced to the "answered threads" pool.