Parameter sniffing, or possibly lack thereof would be my first guess, but really need to see the procedure to say for sure.
Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability