What process are you using? Does this help at all?
http://www.symantec.com/business/support/index?page=content&id=HOWTO42340
Is this more consistent if you run NS.Delta Resource Membership Update? Is there a difference between turning off the test machine, deleting it from the CMDB, restarting PXE and running a delta, and trying again 24 hours later -- as opposed to 2-3 minutes later? Wondering if we can narrow down what's different in the "sometimes works" part of this.
Additionally, have you seen this KB and tried the process within it?
http://www.symantec.com/business/support/index?page=content&id=TECH140403