We present the results of a study investigating the rest-frame ultra-violet (UV) spectral slopes of redshift z~5 Lyman-break galaxies (LBGs). By combining deep Hubble Space Telescope imaging of the CANDELS and HUDF fields with ground-based imaging from the UKIDSS Ultra Deep Survey (UDS), we have produced a large sample of z~5 LBGs spanning an unprecedented factor of >100 in UV luminosity. Based on this sample we find a clear colour-magnitude relation (CMR) at z~5, such that the rest-frame UV slopes (beta) of brighter galaxies are notably redder than their fainter counterparts. We determine that the z~5 CMR is well described by a linear relationship of the form: d beta = (-0.12 +/- 0.02) d Muv, with no clear evidence for a change in CMR slope at faint magnitudes (i.e. Muv > -18.9). Using the results of detailed simulations we are able, for the first time, to infer the intrinsic (i.e. free from noise) variation of galaxy colours around the CMR at z~5. We find significant (12 sigma) evidence for intrinsic colour variation in the sample as a whole. Our results also demonstrate that the width of the intrinsic UV slope distribution of z~5 galaxies increases from Delta(beta)=0.1 at Muv=-18 to Delta(beta)=0.4 at Muv=-21. We suggest that the increasing width of the intrinsic galaxy colour distribution and the CMR itself are both plausibly explained by a luminosity independent lower limit of beta=-2.1, combined with an increase in the fraction of red galaxies in brighter UV-luminosity bins.