Ok so here is what I found. The distance is dependent on the way that the mfccs are calculated. This makes sense to me and also explains why cepstral mean normalization affects the values of the MCD.
I found this implementation (https://github.com/MattShannon/mcd), which unfortunately did not support .wav files. I ran this and it gives results that are in the correct range for its test examples. I looked into the code and found that the the difference was not so much in the calculation of the MCD (which is straight forward) but rather the mfccs. The library I was using gave mfccs at a different scale (I tried python_speech_features and pyspeech). Using the mfccs from Matlab gave me mfccs in a similar range to that of the repo so I opted to use those.
A noteworthy point is that the first coefficient is quite large which is why it is ignored in (https://github.com/MattShannon/mcd) so I did the same. There are some artifacts in the speech I synthesise which likely accounts for why my MCD is still above 10 but its still lower than 30 now.