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 has been rather well understood, the existing approximate formulas fail to describe the correct behavior of Tc for general phonon and paramagnon spectra. Using a controllable approximation, we derive an analytical formula for Tc 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 MgCNi3.