oops Also, did you update the statistics on these tables after reindexing?

If this is coming from a stored proc, I would also do a sp_recompile on the table as well.

I would run it through the profiler and  then run it through the index tuning wizard.  You then may be able to see why it is using the wrong indexes. ...

We run Trend Servprotect on a clustered environment. Why whats up?

Mike