Using density functional theory, we study the lattice dynamical properties of magnetite (Fe$_3$O$_4$) in the high-temperature cubic and low-temperature monoclinic phases. The calculated phonon dispersion curves and phonon density of states are compared with the available experimental data obtained by inelastic neutron, inelastic x-ray, and nuclear inelastic scattering. We find a very good agreement between the theoretical and experimental results for the monoclinic $Cc$ structure revealing the strong coupling between charge-orbital (trimeron) order and specific phonon modes. For the cubic phase, clear discrepancies arise which, remarkably, can be understood assuming that the strong trimeron-phonon coupling can be extended above the Verwey transition, with lattice dynamics influenced by the short-range trimeron order instead of the average cubic structure. Our results establish the validity of trimerons (and trimeron-phonon coupling) in explaining the physics of magnetite much beyond their original formulation.