Hi Stefan,
If you haven't found a resolution to your issue yet, I would suggest beginning to look at other processes on startup. It has been seen (especially on SBS servers) that other processes that are loading on startup push other services back until they finally hit their timeout period. It's possible that one or more of the Backup Exec services are running into this scenario.
Please try the following:
1. As a test, set all other services that load on startup to manual except the Backup Exec services.
2. Reboot the server.
3. If the services now startup fine, then one by one, start enabling the other services that you set to manual in step 1. This will help to identify where the conflict resides.
Please let us know if this resolves your issue, and if not, what errors you're running into now.
Thanks.
Backup Exec for Windows Servers Free E-mail Support
http://seer.entsupport.symantec.com/email_forms/intro_emailsup.asp