You need to look to what the execution plan is telling you for how it's going to resolve this query. Your indexes are not being used or the statistics are out of date possibly.

One concern I have is that you have a number of different UPDATE statements all within a single procedure. When this procedure is called, regardless of the parameters passed to it, all these statements will be compiled based on the parameters passed. This may be causing some of the plans to be created based on bad data. I would suggest treating an IF/ELSE construct like this as a wrapper procedure. Have each of your UPDATE statements in a different procedure. That way, each one gets its own unique plan when it gets called, not all at once.