After server move a query doesn't work anymore
How big are the tables? Sounds like an index problem. Do you have the same indexes on both servers? Did you rebuild the indexes after restoring?

As TiCL suggested, the best way is to compare the execution plans of both servers.