This should easily be solved by running the /registerclient switch using the AeXAgentUtil.exe program located under the \altiris\altiris agent directory. This can be scripted to a remote computer that is experiencing this behavior or run right from the Start > Run area.
"C:\Program Files\Altiris\Altiris Agent\AeXAgentUtil.exe" /registerclient