Constructing a propagation map from a set of scattered measurements finds important applications in many areas, such as localization, spectrum monitoring and management. Classical interpolation-type methods have poor performance in regions with very sparse measurements. Recent advance in matrix completion has the potential to reconstruct a propagation map from sparse measurements, but the spatial resolution is limited. This paper proposes to integrate interpolation with matrix completion to exploit both the spatial correlation and the potential low rank structure of the propagation map. The proposed method first enriches matrix observations using interpolation, and develops the statistics of the interpolation error based on a local polynomial regression model. Then, two uncertainty-aware matrix completion algorithms are developed to exploit the interpolation error statistics. It is numerically demonstrated that the proposed method outperforms Kriging and other state-of-the-art schemes, and reduces the mean squared error (MSE) of propagation map reconstruction by 10%-50% for a medium to large number of measurements.