I suppose that it's possible that an index rebuild could cause a slow down of this nature because of the stats rebuild that also occurs. That may have caused the execution plan to change. I've also see that adding an index (found this out in the code for one of my articles) can cause code to run much slower. The optimizer isn't magic... it was written by humans and it sometimes makes bad choices.

Whatever was the cause, I think you're now to the point where you have to treat it like a new query and tune it. If you want, check the article at the second link in my signature below for how to post what folks need to help you for such problems.