Sounds like this could be a parameter sniffing issue - have you tried:

1) Declare new local parameters at the top of your procedure

2) Assign the values from the input parameters...