When you run the stored proc in SQL Server Management Studio with menu option

Query -> Include Actual Execution Plan

Does the plan show a recommended index to add?

What parts of the query has the most cost?

Sounds like the index is in the wrong place.

Cheers 🙂