In this paper we study the colour-magnitude relation (CMR) for a sample of 172 morphologically classified elliptical and S0 cluster galaxies from the ESO Distant Cluster Survey (EDisCS) at 0.4 less than or similar to z less than or similar to 0.8. The intrinsic colour scatter about the CMR is very small (<> = 0.076) in rest-frame U - V. However, there is a small minority of faint early-type galaxies (7 per cent) that are significantly bluer than the CMR. We observe no significant dependence of Sigma(int) with redshift or cluster velocity dispersion. Because our sample is strictly morphologically selected, this implies that by the time cluster elliptical and S0 galaxies achieve their morphology, the vast majority have already joined the red sequence. The only exception seems to be the very small fraction of faint blue early types. Assuming that the intrinsic colour scatter is due to differences in stellar population ages, we estimate the galaxy formation redshift z(F) of each cluster and find that z(F) does not depend on the cluster velocity dispersion. However, z(F) increases weakly with cluster redshift within the EDisCS sample. This trend becomes very clear when higher redshift clusters from the literature are included. This suggests that, at any given redshift, in order to have a population of fully formed ellipticals and S0s they needed to have formed most of their stars similar or equal to 2-4 Gyr prior to observation. That does not mean that all early-type galaxies in all clusters formed at these high redshifts. It means that the ones we see already having early-type morphologies also have reasonably old stellar populations. This is partly a manifestation of the 'progenitor bias', but also a consequence of the fact that the vast majority of the early-type galaxies in clusters (in particular the massive galaxies) were already red (i.e. already had old stellar populations) by the time they achieved their morphology. Elliptical and S0 galaxies exhibit very similar colour scatter, implying similar stellar population ages. The scarcity of blue S0s indicates that, if they are the descendants of spirals whose star formation has ceased, the parent galaxies were already red when they became S0s. This suggests the red spirals found preferentially in dense environments could be the progenitors of these S0s. We also find that fainter early-type galaxies finished forming their stars later (i.e. have smaller z(F)), consistent with the cluster red sequence being built over time and the brightest galaxies reaching the red sequence earlier than fainter ones. Combining the CMR scatter analysis with the observed evolution in the CMR zero-point we find that the early-type cluster galaxy population must have had their star formation truncated/stopped over an extended period delta t greater than or similar to 1 Gyr.