Despite what you wrote, the first thing to be suspicious of is whether you indeed have all the same fields INDEXED or not. Almost always, something this much slower means the DB is having to do an extensive scan of the actual records instead of being able to work within the indexes.

You don't say what DB your are using. If it's a DB that allows you to view its "execution plan" (example: SQL Server), then do so on both machines and almost surely the differences will pop out at you.