Judging by the timestamp of your post, chances are that you would have aleady found a solution to your issue. If not, here is what you can try.

I was facing a similar issue where in I had a SP which created a linked server, then executed some remote queries and finally dropped the linked server. This SP was working fine when executed from within Studio Manager (I'm using SQL 2005) how ever as soon as I tried putting it in a job it failed with the exact same error message.

I discoverd the issue to be this: The SQL Server Agent on the host machine (my desktop) was configured to run under the "Local System" account. Thus the job was getting executed under the "NT AUTHORITY\SYSTEM" account which ofcourse can not be used to connect to another SQL Server on the domain as it is a 'local' account.

The resolution is to configure the SQL Server Agent services to run under a service account which has the appropriate rights on the remote (linked) server.

Hope this helps.

Regards,

Kuljeet