We prepare two-dimensional crystalline packings of colloidal particles on surfaces of the nematic liquid crystal (NLC) 5CB, and we investigate the diffusion and vibrational phonon modes of these particles using video microscopy. Short-time particle diffusion at the air-NLC interface is well described by a Stokes-Einstein model with viscosity similar to that of 5CB. Crystal phonon modes, measured by particle displacement covariance techniques, are demonstrated to depend on the elastic constants of 5CB through interparticle forces produced by LC defects that extend from the interface into the underlying bulk material. The displacement correlations permit characterization of transverse and longitudinal sound velocities of the crystal packings, as well as the particle interactions produced by the LC defects. All behaviors are studied in the nematic phase as a function of increasing temperature up to the nematic-isotropic transition.