good luck!  I've had an open issue with MS for over a month now, trying to get this figured out.  And I'm only dealing with a one user local MSDE setup.  What I can tell you from my experience, is that if I configure the MSSQLSERVER service to run under a Domain\User account that has admin priveledges to the machine, everything works fine.  When I put MSSQLSERVER back to Local System, it fails every time, regardless of who initiates the job.  The same configuration (Account = Local System) works wonderfully for the other 95% of my users.

  In short, the workaround for me was to set the MSSQLSERVER service to run under the user's WinNT Domain\User account.  Be warned though, that changing the users password may have detrimental consequences.  I haven't tested that.

  If I ever get my schedule to match with my helpful MS engineers' and figure out the problem, I'll let you know.