It is possible that the statistics have changed since a stored procedure was compiled and thus may be executing a less the optimal executionplan, thus it may run slower.
When a procedure is created a execution plan is created, proc is executed according to that execution plan. When we modify the proc it also follow this execution plan. When index is rebuild, new index structure is created, but the proc follows the old execution plan because it was compiled, so there is a chance of unexpected result. For this there is need to recompile the proc.
