I've had similar issues to this where data growth on the system caused a previously high performing query to become very slow.  On investigation I found that it was doing table scans of some large tables in a situation where it should have been doing nested loops as only a very small number of rows were needed.

To fix it I specified optimizer hints forcing the query to use specific indexes which forced the query plan back to the prefered nested loops.  Not a perfect solution as often we don't have time to rewrite or hint our queries to get a specific query plan but it does work.