In paper Convolutional neural network for speech recognition, they say
I didn't understand the highlighted sentence.
In a frequency-like transformation (Fourier, discrete cosine, Walsh), one generally ends up with a sequence of coefficients that account for each frequency component over the support of the basis vector (a segment in time, a 2D patch in images). If you have a frequency component located on one half of the support, and zero the other half, or the converse, you often get the same absolute-valued coefficients. MFCCs fall in that context with:
Information about locality can usually be traced in the phase or the sign of the coefficients, but they are difficult to read in complex situations, and are not preserved with the absolute value or the power.
First you have a misconception in your question which I suggest you to edit first: The paper https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/TASLP2339736-proof.pdf is not authored by Hinton at all.
Second, their statement
As for frequency, the conventional use of MFCCs does present a major problem because the discrete consine transform projects the spectral energies into a new basis that may not maintain locality
They just failed to express themselves properly. The problem is not DCT but that in MFCC scheme you usually drop some coefficients in DCT result. From 40 transformed coefficients after DCT you just take 13 and drop the rest. They take all 40 instead and do not apply DCT transform taking more information. But they failed to explain it, their "locality" is completely senseless.