This is strange, I'd just double-check everything and thats all. If you have enabled language's skill in SkillRaceClassInfo.dbc for your race as learnable, it should work just fine. What faction are those races which get this problem btw in? Horde, Alliance...? As far as I know, changing a faction alignment for race's faction can cause language problems (like, original Horde race can't sometimes use its original language if it was moved to Alliance and so on), but its quite a long time since I had to solve such problems and my memory can be really terrible. I'd say take also a look at your race's factions.
