I was called in once where a procedure went from running in less than a second to many minutes. Since the procedure was called multiple times for each order picked and shipped it impacted getting products shipped.

The problem turned out to be a bad record added to a lookup table. I don't have my notes handy to explain the details, but no one would believe me until they removed the bad record and the problem went away.

I do agree with the previous comment that unless the procedure went across servers then network problems would not be a good answer.