We present new observations of ice nucleation on substrate surfaces that affirm the ``puzzle'' of very high supersaturations required for nucleation from the vapor phase. To explain the observations, the kinetics and thermodynamics of nucleation theory are explored. The results explicitly connect the nucleation to the substrate material's surface binding energy and demonstrate that an improved fundamental understanding must include a strict understanding of the relevant microphysics.