If this procedure has been working fine with good performance then my first suspicion would be that something else is causing the problem.  Perhaps some long running process that is locking the tables that your procedure needs.

As an additional note I would avoid using the exec dbo.spMySP 1,2,3,4 syntax.  Use the command object and specify parameters.  In ADO your method gets passed as a string that has to be interpretted at the server end thereby losing a little performance.

Given what you have said about passed performance it probably isn't a big deal for you, but it is worth knowing about.