This looks like a package problem.
Can you upload package.xml and log.xml for a sample package? You can find them in C:\Program Files\Altiris Agent\Agents\SoftwareManagement\Software Delivery\cache\{GUID} (if memory serves).
Also, if on the Symantec Management Console, you go to Settings, Notification Server, Site Settings, then expand Site Management, expand Site Servers, and select the NS, can you screenshot the Package Service portion and upload?