Sounds like a metallurgical problem. If the part is a titanium alloy then there could be hard precipitates at the surface that appear not to have been peened when actually they have been. Plastic stretching of the surface during peening temporarily removes the protective oxide coating. When this re-forms over a precipitate it could appear dark in color.
