It's now using a bad query plan from the cache.

This exact scenario happened to us. As soon as the bad plan was removed; the sproc started running great again.