Check the sys.dm_exec_requests DMV. What are the long running queries waiting on?
Have you rebuilt indexes recently?
Does recompiling the procedure make any difference? (EXEC sp_recompile 'StoredProcName')
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