Rutherford's model itself has no such problem, because it is based on electrostatic law of force. There is no radiation in electrostatics and thus no radiation implied by the Rutherford's model alone.
But the problem arises when we try to reformulate Rutherford's model in relativistic electromagnetic theory, where changes in EM field propagate with finite speed. We have to replace the electrostatic Coulomb law by Maxwell's equations or similar relativistic laws, which imply that the force acting on the electron is no longer a central conservative force.
Two particles moving in circles around each other means both particles are accelerating. Any particle's acceleration points from the particle to the center of the circle. It is called centripetal acceleration, its value is given by $v^2/R$ where $v$ speed of the particle and $R$ is radius of the circle.
So we have two charged bodies circling around common center point, they produce time-dependent fields and each experiences force due to the other particle; these forces are correlated in time.
In the retarded field variant of EM theory, motion of such system was analyzed by Synge . He found that above decribed motion of both particles implies the distance between the particles decreases in time. Using Frenkel's formulation of EM theory of point particles , which Synge's work is consistent with (although it seems Synge was unaware of it), it is easy to show that for such motion electromagnetic energy is being lost from the region because of EM radiation passing through the region boundary.
If the advanced field variant of EM theory was used instead, the opposite result would have been obtained; electromagnetic energy comes from infinity into the region through the boundary and electromagnetic energy of the system inside this region increases.
The dominant view is that EM fields of such a system should be given by the retarded solution to Maxwell's equations, the advanced solution is usually discarded as unphysical. So such system is expected to lose EM energy, unless something else can resupply it. This something can be, for example, background radiation due to other, external bodies.
 J. L. Synge, On the electromagnetic two–body problem., Proc. Roy. Soc. A 177 118–39 (1940)
 J. Frenkel, Zur Elektrodynamik punktförmiger Elektronen, Zeits. f. Phys., 32, (1925), p. 518-534. http://dx.doi.org/10.1007/BF01331692