Frankly, this souncs like "prepare for image capture" was skipped. Is it possible you ran sysprep manually? If you run sysprep manually, then we don't have a chance to strip the GUID from the agent along with a few other things. It is possible to run Sysprep manually, but we don't recommend it for the exact reason you mentioned above.
Please note that, though there are weaknesses currently with the "prepare for image capture" task, it's still better than a manual run of Sysprep. The only time I'd recommend a manual run of Sysprep is if you also do NOT include the agent in the image. If you do this, we have a method of injecting the agent into the image (which involves really just putting the agent installer "stub" into the image and letting it do it's thing after the image comes up). This would be the recommendation if you need to do some cool things with Sysprep manually and don't want to use our process.
Please verify that you actually ran that step prior to image capture, because that's what it sounds like you did not do.
Oh, and another possibility: please verify that you do not have an actual name in the sysprep file (rather than a random name or something like that) which might force all systems to come up with the same name and thus confuse the crud out of AD as well as NS. This can be checked by looking to see if you have a custom unattend.xml file and looking at it. Ours does the random thing.