Negative differential resistance - a decrease in current with increasing bias voltage - is a counter-intuitive effect that is observed in various molecular junctions. Here, we present a novel mechanism that may be responsible for such an effect, based on strong Coulomb interaction between electrons in the molecule and electrons on the atoms closest to the molecule. The Coulomb interaction induces electron-hole binding across the molecule-electrode interface, resulting in a renormalized and enhanced molecule-electrode coupling. Using a self-consistent non-equilibrium Green's function approach, we show that the effective coupling is non-monotonic in bias voltage, leading to negative differential resistance. The model is in accord with recent experimental observations that showed a correlation between the negative differential resistance and the coupling strength. We provide detailed suggestions for experimental tests which may help to shed light on the origin of the negative differential resistance. Finally, we demonstrate that the interface Coulomb interaction affects not only the I-V curves but also the thermoelectric properties of molecular junctions.