In your case it is pretty clear what the problem is (not so clear for the OP, who had less detail). What you are running into is almost certainly the "Two Hop Rule", which is that under windows domain security, an impersonated security context cannot re-impersonate (that is, it cannot generate the same impersonation on another server).

This is relevant because when you connect from a client to the SQL Server, it impersonates you to generate the security context. In order to get to the linked server using Trusted connections, the security context of your server session would have to be re-impersonated on the target server, and that is not allowed. So even though you can connect directly from your client to both servers, you cannot connect from you client to the first server and then through that to the linked server, because that would be a two-hop impersonation.

The way to test to see if this is really the problem is to find a way to get a session on your SQL server without it having to be impersonated and then try to connect to the linked server from there. I know of two ways to do this:

1) Log on to your server at the console or through Remote Desktop, then run your client to connect to the SQL server on the same box; then connect through it to the Linked Server; it should work now. OR..

2) Write a stored procedure that tries to connect to the linked server and run it using the SQL Agent making sure the the Run As.. is set. (Actually, I am not sure that this still works under Sql2005..)

If you ask Microsoft, they will say that the solution to this problem is Kerberos, but I have yet to see anyone successfully use Kerberos to address this problem in a complex multi-domain corporate enterprise network.

The solution that everyone ends up using is SQL Logins for server-to-server communications. Not ideal, and not a secure as anyone would like, but it does work.