Found out the problem:
When you PXE boot a PC up, it gives it a default PC name, usually the PCs serial / MAC / Service tag #
the problem is, I have hardware where Altiris seems to not be able to get any of that info above, and thus calls the PC "New Computer"
Problem with that is if you try and push a DeployAnywhere / sysprep image to a PC that is like this, sysprep fails because it initially tries to name the PC "New Computer" (based on the sysprep.ini file and using %COMPNAME%)
Now, why would the application itself use a default name it KNOWS wouldn't work for stuff like this? Was a fix released for this?
Also, would changing the default sysprep ini files to %NAME% instead of %COMPNAME% fix the issue?