I would check the security, logins, users etc. Does a user who is a remote login in linked server properties have permissions in these 2 databases? What is the default database for remote login user? We did have somewhat similar problem when linking tables from MS ACCESS when the SQL Server login that was used had a default database different from one we were trying to connect. The solution was to modify ODBC source to change the database when connecting. I do understand that your problem is for SQL Server Linked Server, but check permissions anyway.