I think we have some ways to try fix the problem,
first, as all people says, the maintenance plans are the first step
Second, in the old sql 2005 where the query ran ok, review indexes and statistics created and compare to sql 2005 where the performance is bad.
third, execution plans changed from sql2000 to sql2005, in the old sql2005 where the test run same as sql2000, trace again using profiler and include in the capture, execution plan and compare it to sql 2005 where the querys take a long time, use the same profiler.
fourth, problem in middle tier, if you can, try using sql 2000 in the server where sql2005 takes a long time to return rows, just to verify isn't a network or hardware problem, if you have the same problem as sql2005, may be the hardware need to be tuned, if the response is good, then your hardware is ok and we need check the .NET driver, may be there is some issue.
as gunneyk it may be is a problem in the how sql 2005 complie and re-compilation SPs works, but it think the middle tier
Expect it can help you to find error..