We observe that Cu clusters grow on surface terraces of graphite as a result of physical vapor deposition in ultrahigh vacuum. We show that the observation is incompatible with a variety of models incorporating homogeneous nucleation and calculations of atomic-scale energetics. An alternative explanation, ion-mediated heterogeneous nucleation, is proposed and validated, both with theory and experiment. This serves as a case study in identifying when and whether the simple, common observation of metal clusters on carbon-rich surfaces can be interpreted in terms of homogeneous nucleation. We describe a general approach for making system-specific and laboratory-specific predictions.