A couple of things to check...
First, can you clarify if you are using 7.1 or 7.5? There are major difference between the two.
Do you have all of the plug-in install/upgrade policies turned on. We will start with the Deployment Solution plug-in -- can you verify that it is enabled? What about other tasks, do they run successfully? Next, how are you booting to WinPE? Since you ruled out Automation Folders and Boot Disks -- are you using PXE? -- This is where one of the major differences is between 7.1/7.5 -- at least for the setup.
Are there any errors in the agent log that could suggest what is going on? From the machine that is throwing the error, go to c:\ProgramData\Symantec\Symantec Agent\Logs. Fire off the job again, then check the most recent log entry to see if it gives you anymore clarity.