could be lots of reasons - you really need to try to examine the plan to see what happened. The stock answer is that the underlying data changed sufficiently to cause the plan to be out of sorts OR the parameters that can be passed to the proc are such that the first created plan is not optimal for later queries.
[font="Comic Sans MS"]The GrumpyOldDBA[/font]
www.grumpyolddba.co.uk
http://sqlblogcasts.com/blogs/grumpyolddba/