What version of SQL Server you are in?

It is a known issue SQL Server 2005 SP2. There is a ptch out to fix this issue.

But if you are in some other version. you have to look back at the code to see what you can optimize. Because What I believe that you have a very -2 complex and big stored proc which is trying to delete something.

Divide your sql's into small statements, use temp tables to store intermediate data etc..