I wonder if the procedure hasn't recompiled since your last change and is using an old execution plan? Might want to try doing a freeproccache for s&g's ...

Regardless, have you looked at the execution plan with the procedure and compared it to the execution plan when running it via TSQL?