In addition to what Sean said, the execution plans for the queries would be good to have as well.

Beginning in SQL Server 2005, the optimizer converts IF (SELECT COUNT...)>0 to an EXISTS (see http://blogs.technet.com/b/wardpond/archive/2007/08/27/if-exists-select-vs-if-select-count-1-0.aspx), so the SELECT COUNT query embedded in the IF >0 will likely have a very different query plan than the same SELECT outside of that IF construct.

It could just be that the problematic version got compiled with a new, much more unfortunate plan recently.

Cheers!