Stored procedure execution time went from under 2mins to "infinity" without modifications
I received a follow-up from the database administrator. So I will post his message as the answer.

I tried again after receiving his message and sure enough the stored procedure ran in under 2 minutes.

His email:


  Seems that the issue was a deadlock on the db. I killed the locked processes and it seems fine now. 
  
  The system update essentially caused rehashing in some of the tables and the replication job to your datamart hung up because of this.
  
  Please try again and let me know.




Edit: Additional Information

If you have the same issue, please also consider the comment from @Kin below since I am unable to confirm 100% that the DBA actually did what he said.

@Kin: Well, SQL Server will automatically choose the deadlock victim based on the log usage (the process using less log will be killed unless you have deadlock priority set). I think, it is a blocking issue not a deadlock as thats where you kill the offending process.