We study the interaction of highly nonlinear solitary waves propagating in granular crystals with an adjacent linear elastic medium. We investigate the effects of interface dynamics on the reflection of incident waves and on the formation of primary and secondary reflected waves. Experimental tests are performed to correlate the linear medium geometry, materials, and mass with the formation and propagation of reflected waves. We compare the experimental results with theoretical analysis based on the long-wavelength approximation and with numerical predictions obtained from discrete particle models. Experimental results are found to be in agreement with theoretical analysis and numerical simulations. This preliminary study establishes the foundation for utilizing reflected solitary waves as novel information carriers in nondestructive evaluation of elastic material systems.