A client has the base agent installed. It has also been assigned as a package server. All packages have a 'waiting to retry download' status, including the sub-agents.
Once the client had been assigned as a package server, the NS had included that machine in the available codebases. The source listed for the packages was this particular client itself. Since the package server agent had not downloaded and installed yet, no packages were available but were still looking locally for the executables.
Manually installed the package server agent, AeXNSCPkgSvr.exe from the program files\altiris\ notification server\ nscap\ bin\ win32\ x86\PkgSvr Agent Package folder. To speed things up a little, also did a refresh on all collections. Then the packages started downloading.
NS 6.0 SP3