The skill challenge has been with us since 1.0. We just didn't think of them as skill challenges. Every time a 1978 thief tried to climb a tall wall, that was a skill challenge. As such, this isn't really a new problem. It is an old one - how do you make non-combat situations feel dynamic?
#1: The math still doesn't work in skill challenges. The problem is that the skill numbers vary too much to standardize anything. If you want a skill challenge that really works for your PC group, you need to reverse engineer it based upon the statistical chance of success you want your PCs to have if they use reasonable tactics. That involves some serious math skills...
#2: If you're going to have skill challenges be fun, there has to be a good chance of success, yet a reasonable chance of failure. This creates tension. At least, both success and failure need to seem like possibilities to the players. Most skill challenges suffer from two problems in this regard: a.) The players don't have enough information to measure their chance of success, and b.) Most players don't understand enough about probability to understand how likely or unlikely success is. This is hard to overcome, but you can do it by giving the PCs clear indicators of their progress towards success and failure.
#3: Many skill challenges suffer from repetition of the same skill being used. In negotiations, PCs may be asked to 4 diplomacy checks of DC X before they fail 3. Why all of those rolls? Why not 1 roll? Isn't repetition boring? Isn't repetition boring? Isn't repetition boring?
#4: Most skill challenges fail to give meaning to each roll of a die. The PCs need to see something change every time they roll a die. Each success or failure should change something. That change should be visible to the PCs, be meaningful, and should make sense.
#5: Skill challenges need to keep moving fluidly. Skill challenges are more storytelling than combat - more role playing than roll playing. If you're breaking the rhythm of the encounter to roll the dice, try to minimize that and work the die rolling into the talking.
My only house rule for D&D is going to be a rewrite of the skill system. Skill challenges need to be more fluid. I think the best way to do that is to take the numbers out of a player's hands. You don't need everyone to understand the numbers to keep the game flowing - just the person that has to adjudicate the numbers. It is far easier to get lost in the story of a skill challenge when you don't have to wade through the numbers as much.