This needs a thorough research on stress and intonation including study of alliteration. The basic fast track step in learning sounds. I hope it helps!

See also "L'après-midi d'un phone" by Mallarmé. Weak joke only...

Your intuition seems plausible, but it's flawed.

There are phonemes that are considered common, based on their frequency in languages around the world (see http://wals.info/chapter/18 for a discussion of languages that lack common consonants, consonants in the classes of fricatives, bilabials, and nasals - like your examples of /m/ and /n/.). The hypothesis that common phonemes, or at least consonants, are easier to articulate (the Theoretical Issues section in this discussion: http://wals.info/chapter/1).

Vowels are harder to define, and more subject to change, but there are far more types of consonants than vowels (7 is considered a large vowel inventory while the average number of consonants is 22). Languages with small vowel inventories usually include /a/, along with /i/ and /u/ (http://wals.info/chapter/2).

But, if we accept the hypothesis that easier-to-articulate phonemes are less likely to change than phonemes that require complex articulation, we still have to remember that phonemes that are easy to articulate are members of a class of phonemes. As members of a class, what impediments would there be for one easily articulated phoneme to change into another? /m/ and /n/ are both common nasal phonemes with similar articulation, so what would prevent /m/ from changing into /n/?

Then there is the question of origin. Why do phonemes with complex articulation exist at all? The number of consonants in a language ranges from 6 to 120 or so; vowels from 2 to somewhere in the 20s. There is a general inverse correlation between vowels and consonants, languages that have few of one tend to have many of the other, but there is a strong tendency toward the "average" amounts or consonants in the 20s and vowels close to 10. But what reason is there for the outliers on the high end of either type of phoneme? If phonemes that are difficult to articulate tend to change more than those easier to articulate, there should be a trend where phonemes that are difficult to articulate disappear. But after many thousands of years of language use, they persist in many languages.

The sense that they "persist" is also a problem. The implication is that, the earlier you go back in human history, the more complex the inventory of phonemes was. What would be the reason for this? The alternative, though, is that languages developed phonemes that are more complex in articulation from an inventory of easier-to-articulate phonemes.

Complexity of articulation is also a difficult to define, as it often depends on what other phonemes exist in a language. If language users are comfortable with an articulation pattern based on one phoneme, minor variations on that pattern should be relatively easy to adopt.

But this isn't necessarily true, and has an impact on the hypothesis that ease of articulation should influence the presence of a phoneme (if a phoneme is more resistant to change, it is more likely to be present at any particular time of measurement). Languages tend to "skip" similar phonemes that other languages use. There is very little difference in articulation of an aspirated stop consonant and the non-aspirated version, so little that languages may contain both sounds but not consider them phonemic, but allophones. English has an aspirated /p/ and a non-aspirated /p/. The /p/ in "pit" is aspirated, the /p/ in "spit" isn't. So why doesn't English take the easy route and use these sounds that already exist as phonemes, and maintain them as comparatively easy to produce? Hindi does. But it has its own quirks.

The issue is complex, and I haven't investigated it, but have thought about it. There are real problems with the hypothesis. There's no reason for one easy-to-articulate phoneme to not change into another easy-to-articulate phoneme. Difficult to articulate phonemes should disappear over time - but they seemingly shouldn't exist in the first place. Languages don't use "easy" sound variations that already exist in the language as phonemes, while other languages do use them.

For better inderstanding of the origins of universals in phonetic and phonological systems, see: At the roots of language: Reconstructed fossil vocal tracts and the production of speech. Phylogenetic and ontogenetic considerations. Louis-Jean Boë, Jean Granat, Jean-Louis Heim, Pierre Badin, Guillaume Barbier, Guillaume Captier, Antoine Serrurier, Pascal Perrier, Nicolas Kielwasser & Jean-Luc Schwartz. Contribution from New Perspectives on the Origins of Language. Edited by Claire Lefebvre, Bernard Comrie and Henri Cohen. © 2013. John Benjamins Publishing Company.

James Polichak. Thanks for your helpful and clearly correct explanation, I do understand that ideas of complexity and markedness are difficult to define in a useful way. But do you happen to also know some literature that compares empirically whether some phonemes (regardless of whether they are complex or marked etc.) are in fact more or less stable than others? Or alternatively some literature showing empirically that all phonemes undergo language change at similar rates?

Maybe, in this article you can see changes for sound parameter for sound /a/

http://www.intechopen.com/books/speech-technologies/determination-of-spectral-parameters-of-speech-signal-by-goertzel-algorithm

/r/ often changes into /l/ and vice versa. Furthermore, at least /r/ is often involved in metathesis. It is often claimed that different phonetic realisations of /r/ are complex from an articulatory point of view (and therefore difficult to learn and more likely to change).

For an overview about /r/ in German you might want to have a look at: 

Chapter The Phonetic Variation of German /r/