Marfu,
Thats great.
Have you looked at the execution plan to see what indexes the query is using? If it is doing a table scan, then maybe you need to see if someone has dropped an index (I believe Gail said about that earlier).
Have you run the query through the engine tuning wizard - JUST to make sure nothing has been accidentally dropped...
"Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius -- and a lot of courage -- to move in the opposite direction." - A.Einstein