This was a new one on me:
Backstory: We have an application that runs a SQL job every time a set of data is checked out. (I didn't design it.) Our development server was recently demolished by the SAN team while they were trying to add a new HBA, so it had to be rebuilt from scratch. After the rebuild, SQL was at version 8.0.2039 (SP4 w/ no hotfixes) and the job wouldn't run. It would spit out the above error each time, which was breaking the app.
This error looked like a permissions issue to me, so I started out by checking the user mapping. We'll call the login that runs the application "CORP\AppUser." This user was a member of dbowner in the database in the job step, so that wasn't the problem. Tried sp_start_job from Query Analyzer using those credentials, which worked, but still produced the error. Tried starting the job using my credentials instead, which produced the same error.
Then I changed the job owner to the same account that SQLAgent runs under, and the job worked. So it was definitely a permissions issue. I decided to check out the specific sequence of events underneath firing off a job, so I ran a Profiler trace and found this...
exec sp_setuserbylogin N'CORP\AppUser', 1
Hmm, what's that? It's not in BOL, and I couldn't find it in the master DB. But clearly SQL is trying to execute it, which might explain why the error it's returning is looking for user ''. I dug around a bit more and found some code to add it back into master.
exec sp_addextendedproc N'sp_setuserbylogin', N'(server internal)'
Voila! As soon as I ran this code, the job worked like a charm. Apparently a botched SP3 or 4 install can miss this proc, which is what probably happened here. So if you come across this error, make sure you've got sp_setuserbylogin properly installed.