"There were lots of people on the other side of the transaction, too. "
Absolutely. When you look into the current crisis, you'll notice that it isn't a crisis of "net loss". This crisis is just redistribution of money - for each loser there is a winner. No money or value was "net lost", instead it was redistributed. For each homeowner "B" who bought overpriced house, there is a previous owner "A" who made nice profit which is pretty much equal on average to what mortgage note holders lost when "B" foreclosed.
" The money paid to the collectors of the CDSes did not come out of thin air, after all."
Again, absolutely right. The CDSes were paid by taxpayers - government bailout of AIG and others. So what taxpayers lost, CDS holders won (as they are just better politically connected, surprise!). No net loss again.