Here's a thought: treat joining a new core class just like joining a prestige class. That is, give them requirements reflecting the training that goes into the class, and make it more costly for classes who would gain the most out of them. Here's my attempt at it:
Barbarian: Martial Weapon Proficiency, Toughness, Intimidation 4+, Survival 4+, Any non-lawful alignment.
-Barbarians are about being strong and tough, which these requirements reflect. Classes without Good fortitude saves or appropriate skills will have more trouble adapting to this way of life. You can require the PC live with a tribe or have some other cultural involvement, but it doesn't seem necessary as a rule.
Bard: Skill Focus (Perform), Perform 4+ ranks, Ranks +1 of any 4 knowledge skills, Ranks +1 of any other four bard class skills, besides craft or profession, Any non-lawful alignment
-The magic of music is open to those with great skill in it... and a bit of skill in lots of other things
Cleric: Simple Weapon Proficiency, Skill Focus (Knowledge Religion); Ranks 4+ of the following: Concentration, Heal (or domain related skill), Knowlege (Religion); Appropriate alignment
-Those faithful to their diety can learn to ask for their power, if they deem themselves worthy by dilligence and conduct.
Druid: Skill Focus (Knowledge Nature); Ranks 4+ of the following: Animal Handling, Concentration, Knowlege (Nature), Surival; Any Neutral Alignment, special
-Besides an understanding of nature, druids must also properly repect nature, and refrain from the use of metal armor.
Fighter: Martial Weapon Proficiency, any two feats from the fighter list
-Fighters need to be able to, well, fight. As long as they can use weapons, and put effort into their martial abilities, it should be open to anyone. Armor proficiencies from just being in a class shouldn't count towards the feat requirement.
Monk: Improved Unarmed Strike, Run, Balance 2+, Climb 2+, Jump 2+, Tumble 2+, Knowledge (Arcana and Religion) 2+, Any Lawful Alignment
-Monks train not only in unarmed combat, but also a wide range of skills. PCs of any class looking to join monk will need to invest in at least some cross class skills.
Paladin: Martial Weapon proficiency; Ranks +2 in the following skills: Heal, Knowledge (Nobility/Royalty and Religion) and Sense Motive; Lawful Good alignment, Follow the paladin's Code
-Paladins require training of their body and mind, but above all else are about dedication to the divine prupose set before them. In addition to the other requirements, a prospective paladin must abide by the paladins code unwaveringly.
Ranger: Martial Weapon Proficiency, Track, Endurance, Ranks 2+ in Handle Anima, Survival, Knowledge (dungeoneering geography and nature)
-Rangers can be lots of things, as long as it involves being an able warrior and skilled outdoorsman it should be good enough.
Rogue: Simple Weapon Proficiency, Skill Focus in any one and 2+ ranks in any four rogue class skills, except for craft or profession skills.
-Rogues come in all types, the only thing they truely have in common is a great emphasis on skills. Classes that are natural skilled will have little trouble going rogue, as it were. An appropriate +2/+2 feat such as agile could replace the skill focus requirement.
Sorcerer: Magical Aptitude, Ranks 4+ of the following: Concentration, Knowlege (Arcana), Spellcraft.
-Discovering a talent for magic after following another path takes effort and study, unlike those who discovered it when younger.
Wizard: Skill Focus (Knowledge Arcana); Ranks 4+ of the following: Decipher Script, Knowlege (Arcana), Spellcraft; the ability to read and write.
-Would be wizards need to spend much effort on the lore of magic before they can learn to manipulate it.
This doesn't do that much to limit the power of multiclassing, but it keeps the characters consistancy in check. I aimed for the requirements to be open to at least some characters at level 2, and open to anyone eventually, requiring feats the class would grant anyway or that reflects the extra effort invloved in training (perferably thematic and weak

), and some training in the iconic skills of the class. I used only feats from the PHB, other sources could have ones that are more appropriate. Expecialiy for the casters, feats that provide some limited spell ability or caster level would be perfect. Some kind of divine feat for paladins would be good too.
If you want to limit the power of multiclassing, you could also take out some of the immediate benefits, such as the +2 to good saves and/or the automatic proficiencies