I have encountered an issue with Cycles Volumetrics in a recent scene. I am using Blender 2.72, and both CPU and GPU render options. In both I get a solid black artifact when I have two volumes overlapping, as in this campfire smoke test:
I have a solid cube, with a volume scatter and volume absorption material, duplicated by a particle system. As you can see, when the particles get higher up and farther apart, and are no longer overlapping, the artifacts disappear.
Try increasing the number of Transparent bounces in Render settings > Light paths:
The reason this happens is because when there is nothing plugged into the surface output of the material output node, it behaves like a transparent shader. When a ray goes through a set number of transparent surfaces (as defined by the value in max bounces), it will stop and just return nothing (resulting in a "black surface").
To avoid these black surfaces, ensure that the max bounces are high enough. Note that forcing too many bounces can cause a noticeable slowdown when rendering due to the extra bounces which need to be calculated. This is especially true when setting the number of min bounces as well, and in cases which allow high numbers of bounces before the ray can escape to the sky (such as an indoor scene).
