I used to struggle with this issue from time to time. One of the things I basically did was as suggested above by the_orc_within - you basically split up every stat into constituent parts, and that means that someone with a high stat will mechanically do better in things linked to that stat overall, but you can still roleplay they they have a flaw somewhere, and people with a low stat will do worse overall in things linked to that stat, but might have one silver lining. There's no need to make this mechanical (D&D 2E Player's Options tried to, and I didn't really like it personally) - it is a good way of explaining roleplaying results for mechanical decisions, though.
One thing that I don't think has been mentioned enough in this thread is the role of the DM in this area, and just how much power they have to make or break this whole area. One thing I found incredibly helpful in this regard was a passage in Tracy Hickman's book Xtreme Dungeon Mastery (which you should all rush out and buy, so I get more levels). Tracy points out that as the DM, you of course have the authority to make the game world bend to make smart characters smart, wise characters wise and charismatic characters charismatic, even if their players are not as smart, wise or charming.
What do I mean? Take the classic intelligence problem - you have a puzzle that needs to be solved by the characters (ie not one that is meant to tax the players alone, but their characters specifically). A is playing a wizard with a high intelligence, but isn't that smart. B is playing a barbarian, but in real life has a PhD in astrophysics.
Player B, of course, thinks he knows the answer, and so suggests turning knob X and fiddling with the dials until they all point south east and create congruent triangles. Even though it makes perfect sense, for some reason it doesn't work.
Player A doesn't really get how this whole thing is meant to work, but he suggests maybe it's a magical flux created by puppies, and offers the pedestal walkies. Amazingly, the door opens!
What happened there? The puzzle worked the way the smart character thought it would work, because he's smart.
If you wanted to roll an intelligence check for both of them, that's fine - probabilities are that the wizard will succeed and the barbarian will fail.
This isn't a stand-alone solution obviously - but I find it good for putting players in their place when they think they know it all, and can solve it all, because they are smart, witty and charming in themselves. Players of moderate wisdom in my games always feel wise, because their characters just happen to regularly make decisions that work out, sometimes changing the nature of commonsense itself in the game world.