We reconsider the long-standing problem of the effect of spin fluctuations on the critical temperature and isotope effect in a phonon-mediated superconductor. Although the general physics of the interplay between phonons and paramagnons had been rather well understood, the existing approximate formulas fail to describe the correct behavior of $% T_{c}$ for general phonon and paramagnon spectra. Using a controllable approximation, we derive an analytical formula for $T_{c}$ which agrees well with exact numerical solutions of the Eliashberg equations for a broad range of parameters. Based on both numerical and analytical results, we predict a strong enhancement of the isotope effect when the frequencies of spin fluctuation and phonons are of the same order. This effect may have important consequences for near-magnetic superconductors such as MgCNi$_{3}$