As mentioned we only needed to register the one DLL ot resolve our issue, it wasn't happening on all machines though, maybe up to 35%.
Symantec sent us the following sugestions to try which includes the DDL register you've already tried, it might be worth a go on a couple of machines;
As discussed in our previous phone conversation, here are the instructions on how to unregister and re-register the Client Task Agent.dll and the CTAgentUI.dll, which will hopefully resolve the problem.
Please execute the following commands one by one on the Site Server:
C:\Program Files\Altiris\Altiris Agent\Agents\Client Task Agent>regsvr32 -u "Client Task Agent.dll"
C:\Program Files\Altiris\Altiris Agent\Agents\Client Task Agent>regsvr32 -u CTAgentUI.dll
C:\Program Files\Altiris\Altiris Agent\Agents\Client Task Agent>regsvr32 "Client Task Agent.dll"
C:\Program Files\Altiris\Altiris Agent\Agents\Client Task Agent>regsvr32 CTAgentUI.dll
If this does not work, run the same commands on one of the affected clients and see if it helps resolving the issue.