Hello,
Refer the following technote to troubleshoot this problem:
When trying to start Backup Exec, the following error may be encountered: "The Backup Exec Server system service is not responding. The service is not running or not installed."
http://support.veritas.com/docs/267326
NOTE : If we do not receive your reply within two business days, this post would be marked assumed answered and would be moved to answered questions pool.