Answer
Symbols derived from BMP pictures are converted to vector when used in ArcMap. This conversion is slow because it is done pixel by pixel and the result is a large output file. To avoid this, use existing symbol sets, or design your own based on those that are provided in the symbol set.
This only applies to picture symbols in 8.0.1 and 8.0.2, as they support raster. In 8.1 raster is no longer converted to vector.