Not knowing much else, I can make too guess. First, the indexes need to be rebuilt or your statistics are out of date. This can lead the optimizer to make poor choices or the correct choices the optimizer makes don't work that well. Also, you could just be seeing an instance where the optimizer is not making the best choice. The optimizer only spends a certain amount of time evaluating plans and decides on the best plan based on cost estimates. It's not always correct. It's just mostly correct.

I couldn't say anything more specific without seeing the execution plans, the query and possibly the structure.