Mark@Altiris, do you include the Application Metering Agent on your affected machines? If so unregister AeXAMAgent.dll (regsvr32 /u "C:\Program Files\Altiris\Altiris Agent\AeXAMAgent.dll") and then try starting the service again. I think that's the path, I don't have any machines to confirm on as we have the same issue when it's installed.
Edit: Path may be "C:\Program Files\Altiris\Altiris Agent\Agents\Application Metering Agent\AeXAMAgent.dll", found that on an XP machine where AM still works.