Go under Library Master --> Main --> User Maintenance. Pull up the user and click tab 2 (Preferences). The last option on the right, "Spawn Tasks from Application Server" --> make sure this is checked. I'm not sure if you have to close Sage and re-open to take effect but do it anyway for that user just to be sure. Then try it again.

Thanks for the reply. Unfortunately, this was already checked on the one user that has been the biggest offender to this so far.

It is at the Printing (to Paperless) stage, or at the Updating stage?  If the PDF is not being produced, double check the lockfile setting in PL_AdvancedOptions_UI

See KB article 59838 for details.

If the problem is at the Updating stage, make sure you have AV exclusions in place.

Thanks, I will look in to this. Other thing I thought of last night... I'm don't really know the technical details of how PL works, but if they are selecting a "local" printer (one that says redirected after its name), instead of a printer on the terminal server (like Print to PDF), could this be the problem?

Yes.  PL uses a real print object (the "default" for the session) to determine things like page size, and a bad / missing driver can cause problems.