In short, soft bodies are *compressible* while cloth simulation is not. All other features are the same.

However, this makes a huge difference in computational speed. To better explain this, I will use an extension of the metaphor CharlesL used in [his response][1].

A **cloth simulation** essentially models the object as a bunch of balls (vertices) connected to each other by fixed-length rods. Thus, for computational purposes, the simulation can treat the internal distances between points as a constant, and *only has to calculate interaction with other objects.*

**Soft body simulation**, on the other hand, models the object as a bunch of balls (vertices) connected to each other by springs. So now, not only does Blender have to compute the interaction of the object with other objects, but also has to compute its own internal reaction and the spread of force applied at one point across all of those little springs, which is *much* more complex.

I don't know the exact complexity of the algorithms Blender uses for these simulations, but it's essentially the difference between a linear relationship and a differential equation.


  [1]: http://blender.stackexchange.com/a/1434/25