Sorry marfu, but without seeing the structure of your tables, indexes etc it is difficult to see why this could be happening.

How big is the actual table? If you look at the execution plan, you could see which indexes it is using and try to rebuild those first...Providing no-one has deleted an index, then it should just be a case of rebuilding the stats (a reindex will do that for you, so there is no need to run a stats rebuild if you are reindexing) or re-creating the index if it has been deleted - you could try running the query through the engine tuning wizard and build any stats/indexes it recommends.

I wouldn't normally recommend that, but as I can't physically get my hands on the server, its tricky 😀