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.