This post is in two sections - design theory and houserules. Skip to the section you find interesting.
Design Theory
Many of the problems with Skill Challenges have everything to do with design and nothing to do with rules. The first of these is complexity. A Skill Challenge is interesting when it governs scene resolution instead of task resolution. For instance, "Convince the guard to let you through" is inherently not an interesting skill challenge. It's painfully binary (you either get through or you don't), there's no sense of progress and the approach is beyond obvious (Diplomacy,
maybe Bluff or Intimidate). You're better off just rolling a single check and moving on.
Adding some complications helps; "Convince the guards to let you through for free and without sounding an alarm" is better. You now have several different narrative options for failure, the players can feel a sense of progress by checking off mitigated complications, and more skills make sense (Bluff and Intimidate are now definitely in, and I could make cases for Stealth, Perception, and Insight). As a rule of thumb, add one level of numerical complexity for each complication beyond the first - so this would be a Complexity 2 (6/3) challenge.
Even better, though, is "Infiltrate the castle, determine where the chancellor is and and get him to drop his charade" - a Complexity 3 (8/3) challenge. The characters can now sneak in, break in, disguise themselves, bribe people, whatever - far more options for paths (and thus skills!) than before.
Another major issue with runnning an effective Skill Challenge is to not make every single action a roll. This is particularly important under two circumstances: a) the action is uncontested and/or b) you don't know what a failure would look like. As an example, swimming across an empty, placid lake should not be a skill check. There's no conflict - no monsters under the water, no undertows. no currents. - so it's an uncontested action. Furthermore, what would happen if he failed - would he drown? Say "yes" and move on. Don't get caught in the mental trap that any action with an opponent is contested! imagine a common "haggling with the merchant" scene next. The character takes her desired item to the merchant and opens negotiations with something like "Are you willing to lower your price on this?" Presuming you have a society where bartering is common, this doesn't need a Diplomacy check, even in a skill challenge. The NPC is already accustomed to banter with customers and readily engages her - save your skill checks for something more pivotal. A skill check, whether in a challenge or on its own, should be a point of legitimate conflict. Besides building drama, spreading out the skill checks over a larger number of character actions helps hide the mechanics under the narrative.
This leads us to the next design point, although we've already hit it a couple times obliquely so far - a skill challenge that stops the story is invalid. If your characters must complete the challenge to proceed with the plot, your challenge is invalid. Rewrite it with complications such that if they fail, they can still move on with the game.
As much as possible, narrate successes and failures in linear time, with each one building off of the previous, even if the players all rolled at the same time. Nothing makes a skill challenge seem stupid faster than multiple checks whose outcomes seem utterly unrelated. I'm also in the camp that believes you should not tell the players the complexity of the skill challenge, nor the primary skills. Your players may very well come up with a use for a skill that you didn't think of that is entirely reasonable to acheiving the goal(s); outright stating the primary skills tends to squash those moments of brilliance. Also, require that a player state what the character is actually doing before making a skill check. "I roll Diplomacy" doesn't cut it - and yes, I do have a technique or two for players who can't seem to think of anything.
My final thought in this section is the use of success and failure tokens. When adjudicating a skill challenge, I do not verbally indicate successes and failures. I have a supply of little red and green chips that I'll drop on the table as successes and failures accumulate, but I never use either of those words. I continue to narrate the world or speak for an NPC with as little interruption as possible and let the players do the counting for themselves. It seems silly, but I've found it's very helpful in maintaining immersion both because the narrative doesn't stop and no one has to ask how many successes or failures they've racked up so far. It also seems to help associate the success or failure with the action rather than the dice roll, since I can drop the chip anytime I like after the roll is made - my players can trust that they'll clearly know the mechanical outcome and can better focus on the game world.
Actual Houserules
Now that's not to say that all of the failings with skill challenges are design issues. I have a few houserules as well that I feel address mechanical issues with the skill challenge system:
Bonus Tokens - One of the major failings of the system is that characters with the wrong skills can only hurt the party's chances of success. If your challenge is broad enough this shouldn't be an issue, but occasionally it will pop up. Furthermore, you want to always recognize a good die roll. A character who earns a success on a non-primary skill is handed a (purple, in my case) Bonus Token. The Bonus Token(s) can be used to negate a failure, grant an ally a reroll or +2 to an already rolled skill check or add some new fact to the story of the challenge. For example, a cleric earns a Bonus Token on a Religion check by praying for divine intervention during an urban chase scene. When the party's rogue fails an Acrobatics check to leap from roof to roof, the cleric's god arranges for a cart full of hay to break the rogue's descent and prevent falling damage. This is different from the DMG2 version of Secondary Skills in that it gives the player the opportunity to define and use the boost when it is helpful (not just immediately), making him or her feel more useful. It also allows the players to have more narrative control of the game. This is good for players who have trouble roleplaying their skills - letting them come in whenever they have a decent idea helps out a lot.
If you like, Fallout Tokens (which the GM gets when a player fails a non-primary skill check or the challenge itself passes a non-primary skill check) can be used to inflict similar penalties on the party.
Active Resistance - As Saeviomagy points out above, skill challenges that don't "bite back" are sleep-inducingly boring. Many of my challenges get "actions" each round equal to half the number of PCs. The challenge can use these actions to make its own skill checks (inflicting Fallout or Failures), usually against a PC's defenses or Passive skill (any given skill +10), or force a PC to make a roll he or she wasn't expecting. A timer, like Stalker0's 3-round Obsidian system is a form of Active Resistance where the challenge automatically chalks up a Failure each round of its own accord. This is another trick to deal with problem players - characters who have been "hit" by a skill challenge often find something they'd like to do in retaliation or to remedy their problem. It's a hook, really.
Resource Management - Players can use other resources to help them with their task:
- Bold Recovery- A player may spend an action point to reroll a skill check they have made, before they might know if the roll was a success or failure. The player must take the result of the reroll.
- Brazen Action (Combat or Active Resistance only) - Once per challenge, a player can take a ‐2 to all defenses. He gains a +2 to all skill checks related to a skill challenge. The benefits and drawbacks last until the beginning of his next turn.
- Power Hungry - The player may use and roleplay one of his or her Powers that is normally a combat ability to gain a bonus to a skill check based on the power used. Encounter powers give a +2, Dailies give a +4. Really inventive uses of an at-will might garner a +1, but this is the exception, not the rule. See “Off the Grid” on the At-Will Blog for examples.
- Last Gasp - When the group has only one Failure or one round left, any character may spend a healing surge to gain +3 to a Primary skill check.
So there's my thoughts on the matter. Hope it gives you all some ideas.