We we ran into the same issue and even brought in Altiris/Symantec support. (Yes, we stumped them)
It turned out that it was the name of the NS server.
The server was named altiris_ns and when we changed it to altirisns the issue went away.
The is a Windows 2003 R2 Ent. with Sp2 and has SQL 2000 Sp4 with the latest hot fixes. NS is 6.0 Sp3 with hot fix 8.
