Is Backup Exec installed on a MSDE or SQL instance?
Are the Backup Exec services (apart from Remote Agent for Windows Servers service) started with Domain Administrator Account?
Try starting the services with Local System Account..
Any error in Application Event Log?
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.