The job that's failing is the one descibed above that executes an application using xp_cmdshell.  The path is still valid, access has not changed, and the application works fine when...

Yep, same results in QA regardless of the credentials used, whether using xp_cmdshell or 'exec sp_start_job...'