Irda Ranger said:
This is a neat way to look at game design, but I don't think it's the source of the problem you describe. Like others up thread, I think flavor should come first but that a positive feedback loop between both is necessary to end up with a playable game.
Your problem though is primarily with PCs that were designed for a different campaign then the one they find themselves in. Or maybe your problem is more generally with class design that's not universally useful in all kinds of campaigns.
Not really. Campaigns change. What works at one point may not work at another. With inflexible, flavour first mechanics, you are stuck with what you started with. Granted, the Retraining rules from PHB 2 go a long way to helping here.
But, you mention the paladin being unhappy about leaving his mount behind. Now, here's another textbook example of what I'm talking about. In earlier editions, you had to quest to get your mount. Great, fantastic flavour - the chosen of the gods goes out to secure his trusty steed.
Then came play at the table. What does the rest of the group do while Mr. Paladin goes out to get this mount? It's the Decker problem from Shadowrun all over again. (well, actually predating the decker issue by quite some time really

) And, after Mr. Paladin gets his steed, what does he do with it? Most adventures don't allow for horseback riding. Unless you happen to be doing outdoor adventures in fairly clear terrain, horses are pretty much useless.
3e helped a bit here by making the mount summonable, but, again, it was keeping the flavour without sitting down and looking at the game first. Mounts in D&D, by and large, are rarely used. Other than for traveling from A to B, you don't see them too often. How many PC's took Mounted Combat in your campaigns? I think I saw it once, maybe. Why? Because the vast majority of adventures are not mount friendly.
A game first approach would think, "ok, what do adventuring PARTIES (not individual PC's) do? What does a paladin need to help him do that and act within the party? Would a mount help? Is a mount a good idea for a fairly major ability for the class?"
If the answer is no, then the mount is simply not added and you go with something else.