Also, if a skill works, players will usually just repeat it. Having a diplomatic encounter and have the players just roll diplomacy 8 times seems kind of lame. Defeating a trap by making eight thievery rolls might be neat if you are also in the middle of combat, but it still is a little weird. Are characters supposed to figure out what skills to use and never be told? Players may be afraid to make rolls with skills since they might get a failure, but some skill rolls don't create failures but modify other rolls or open up new paths.
Okay, some quotes from the compendium:
"The DM either informs the players when the challenge begins or lets it begin quietly, when an adventurer makes a skill check that the DM counts as the first check of the challenge."
So you can announce it or not announce it. Seems reasonable.
"As the challenge proceeds, the DM might prompt the players to make checks, let them choose when to make checks, or both."
I think the intent is to make things very free form. But what I have realized I don't like is DM prompted checks without consequences. Maybe if I ask for a check I mark up a success up a success/failure counter.
"The DM might tell the players which skills to use, let them improvise which ones they use, or both."
Yup, really free form which allows you to have good skill challenges and bad skill challenges. A little bit like combat, but combat has a minimum level of fun. Making a boring skill challenge is much easier.
Okay, so like I started talking about before. A good skill challenge must involve player decisions. If the only decision is what skill to use this is dangerous because players will probably just use the skill that works. Negotiating with a king? Sure, you could use History to impress him with your local or Insight to sense what kind of approach would work, but it terms out you have a Bard with a high diplomacy roll so why not just do Diplomacy every time.
So I popped open the DMG to look at the examples and starting reading "Running a Skill Challenge". Originally it forced every character to make a roll, but the errata changed this. That makes the first example "The Negotiation" meaningless. Instead of forcing every character to find some skill that might be helpful you can just have your diplomacy expert do the talking and rack up the 4 successes you need. The same is true of several of the other examples.
This turns a skill challenge into a standard skill roll and that is lame. One solution is to limit the number of successes you can get with one skill, but you will have to deal with a 'huh' look from players because that is kind of arbitrary. "What do you mean Diplomacy no longer works on the Duke and I have to use another skill?"
Another option could be to have an increasing penalty. Each successive roll with one skill causes that skill to be used at a cumulative -2 for the rest of the encounter. That way the characters will have a more organic reason to switch and the switch will be a tactical decision instead of a restriction.
I guess the basic question is how do you make a skill challenge fun and not just a roll-fest. I think it comes down to two things: Decisions and State. Players have to have some decision to make or they are just guys who roll dice and observe. In the basic idea of the Skill Challenge the players have to decide what skill to use and figure out what skills make sense to use. Unfortunately this often fails for the reasons mentioned above, you find the best or most obvious skill and apply it until you succeed. So you need to put in some reason to use something beyond the initial skill. I mentioned above the -2 penalty at a simple option.
State is the other requirement. The simplest form of state is tracking successes and failures. Having even this simple, kind of abstract counter makes it feel like a roll is important.
If you think about combat, every round the character makes decisions, probably rolls some dice based on those decisions, and then sees the state of the battle change. In battle the decisions are more complex as is the state making the game fun. The more decision making and state change in a skill challenge the better. So when you design or analyze a skill challenge those are the two basic factors you have to keep in mind.
So I going to look at more skill challenge examples, but my initial impressions are that highly specialized skill challenges are the good ones. Ones that have some concrete story and effects around them. Unfortunately, the most useful skill challenges would be generic ones, like negotiating with someone, getting information from a prisoner, or traversing the wilderness.
One thing this makes me think of is the mini games in Mass Effect where you have to complete some sort of mini-game to open a lock or decrypt some information. Figuring out a mini-game for various activities might be possible, but it has the potential to take you too far out of the game. Solve this Sudoku to successfully interrogate the prisoner seems a little weird.