Learning foreign speech contrasts involves creating new representations of sound categories in memory. This formation of new memory representations is likely to involve changes in neural networks as reflected by oscillatory brain activity. To explore this, we conducted time-frequency analyses of electro-encephalography (EEG) data recorded in a passive auditory oddball paradigm using Thai language tones. We compared native speakers of English (a non-tone language) and native speakers of Mandarin Chinese (a tone language), before and after a two-day laboratory training. Native English speakers showed a larger gamma-band power and stronger alpha-band synchrony across EEG channels than the native Chinese speakers, especially after training. This is compatible with the view that forming new speech categories on the basis of unfamiliar perceptual dimensions involves stronger gamma activity and more coherent activity in alpha-band networks than forming new categories on the basis of familiar dimensions.