While I was migrating my database server from SQL 2000 to SQL Server 2005 I came across this error as the production and development environment were not quite identical.
Well the first thing to note in this error is non descriptive, preventing information disclosure to unauthenticated clients.
To determine the true reason for the failure, the administrator can look in the server’s error log where a corresponding entry will be written. An example of an entry is:
2006-02-27 00:02:00.34 Logon Error: 18456, Severity: 14, State: 8.
2006-02-27 00:02:00.34 Logon Login failed for user ‘<user name>’. [CLIENT: <ip address>]
A great article with the complete description of this error and states is written by Il-Sung Lee here: http://blogs.msdn.com/sql_protocols/archive/2006/02/21/536201.aspx
Happy working with your linked servers.