It's finally solved.

Our network guy who(m) is much more clever than me added an entry in the PATH variable and it magically started working. Apparently the pdfcombine program was having troulbe finding the license info.

One interesting that that was discovered:

Run the following: EXECUTE master.dbo.xp_cmdshell 'SET'

and then run SET from the command prompt. (make sure you are logged in as the account that the agent is running as). For me it's returning different things in the 'PATH' variable.