Something is grieviously broken, but I don't have enough information to tell you what is broken or how it should be fixed.
The first step would be to attempt the same query the new server using Query Analyzer. The purpose of this step is to determine if the problem lies in the connection between the two machines or within the SQL Server itself. If the query runs poorly in Query Analyzer, then the problem is in the connection between the machines (something is impeding SQL communications between them). If the query runs acceptably in Query Analyzer but does not using the linked server, then the problem is in the linked server.