Diachronic velar palatalization is taken as the case study for modeling the emergence of a new phoneme category. The spread of a palatalized variant through the lexicon is treated as a stochastic classification task for the listener/learner. The model combines two measures of similarity to determine classification within an exemplar-theoretic framework: acoustic distance and phonotactic expectation. There are three model outcomes: contrast, allophony, or contextual neutralization between the plain and palatalized velars. It is shown, through a series of simulations, that these can be predicted from the distribution of sounds within the pre-change lexicons, namely, the ratio of the /k-vowel/ sequences containing naturally palatalizing vowels (i, I, e), to those containing non-palatalizers. "Unnatural" phonotactic associations can arise in individual lexicons, but are sharply limited due to the large size of the lexicon and the local nature of the phoneme changes. "Anti-natural" distributions, which categorically violate the proposed implicational relationship between palatalization and frontness/height, are absent. This work provides an explicit and restrictive model of phoneme change. The results also serve as an existence proof for an outcome-blind mechanism of avoiding over-generation.