It sure sounds like a blocking issue. How are you checking for block connections? SEM? sp_lock? If you're using SEM, try sp_lock instead. You'll probably have to execute the proc a couple of times.

Try using Perfmon and the SQL Server:Lock Object. Look at the Average Wait Time counter.

Did you change the Isolation Level? Is the disk that contains the TLog healthy. When a command query executes, data is modified in SQL Server's cache but a record of those modifications is written to the disk. SQL Server will wait for the ACK from the IO subsystem before considering the query successful.

This is just stuff off the top of my head. These kinds of problems can be very difficult to track down.

Good luck!

-Mike