According to http://grammarist.com/usage/overtones-undertones/ your understanding of the common usage of these terms is correct.
Grammarist.com does point out that when these terms are used as musical jargon, they have distinct meanings. According to Grammarist.com, overtones are higher-pitched harmonics, whereas undertones are hushed noises.
It seems to me that it is a coincidence that these synonyms have opposite prefixes. Other prefixes (like "side") could have been used, but were not. ("Sideband" and "overtone" have similar technical definitions.)
Both technical meanings are similar in that they refer to secondary noises that can be hard to notice, but are present if you listen for them. The common usage of these terms emphasizes this meaning, so they are synonyms in common usage.
Each technical meaning has a plausible reason for using the prefix it uses. "Overtone" uses "over" in the sense of "higher", and "tone" in the sense of "pitch". "Undertone" uses "under" in the sense of "less loud", and "tone" in the sense of "audible noise".
"Oxymorons" are similar to this kind of paradox.