We investigate the temperature dependence of photon coherence properties through two-photon interference (TPI) measurements from a single quantum dot (QD) under resonant excitation. We show that the loss of indistinguishability is related only to the electron-phonon coupling and is not affected by spectral diffusion. Through these measurements and a complementary microscopic theory, we identify two independent separate decoherence processes, both of which are associated with phonons. Below 10 K, we find that the relaxation of the vibrational lattice is the dominant contribution to the loss of TPI visibility. This process is non-Markovian in nature and corresponds to real phonon transitions resulting in a broad phonon sideband in the QD emission spectra. Above 10 K, virtual phonon transitions to higher lying excited states in the QD become the dominant dephasing mechanism, this leads to a broadening of the zero phonon line, and a corresponding rapid decay in the visibility. The microscopic theory we develop provides analytic expressions for the dephasing rates for both virtual phonon scattering and non-Markovian lattice relaxation.