Like Jeff already suggested: it might be required to recompile the code since the cached query plans might still not reflect the new index.

Jeff suggested the DBCC FREEPROCCACHE followed by a DBCC DROPCLEANBUFFERS.

That's the very first time I disagree with him (and most probably I'll be proven wrong...) :blush:

I'd rather go "step by step" and start with a single sproc that I know performs badly.

Recompile this sproc separately either by using the option WITH RECOMPILE or by running EXEC sp_recompile N'yourSchema.YourSproc' and verify this will actually help to improve performance.

Once you know that recompile is the solution you could either recompile the sprocs and queries step by step or run the DBCC FREEPROCCACHE followed by a DBCC DROPCLEANBUFFERS as suggested.