Is the database local to the LD server or is it on a remote server? Are the services and com+ objects configured to use a domain account?
The database isn't local it is located on our SQL server. The SQL server is rebooted 40 minutes before the LANDesk server is rebooted. The services and com+ objects are configured to use a local accoun. Let me know if you require any more information.
My thought was that connectivity to the sql server or account authentication might be part of the issue. If an account can't connect or be authenticated then the service would fail to start. I've ran into this problem with boot sequences in the past. I'd start by going over the event logs at boot time to see if there is an event message that might relate to the failure. Also check the logs in Program Files\LANDesk\ManagementSuite\log, specifically LDInv32.log and see if there is anything to indicate a failure.
Side note, you could try setting actions on the recovery tab of the service.