if it went a way after altering the proc, and then came back after a few hours, i'd start suspecting that stale statistics were affecting performance of the existing plans;
if you look at the tables used by the proc, are any of them MillionBillionRow tables and have a large amount of insert/updates/deletes to them?
can you update statstics for the tables used by teh proc and see if there is an immediate improvement?
help us help you! If you post a question, make sure you include a CREATE TABLE... statement and INSERT INTO... statement into that table to give the volunteers here representative data. with your description of the problem, we can provide a tested, verifiable solution to your question! asking the question the right way gets you a tested answer the fastest way possible!