In a word, yes. I love skill challenges when they are done right. The problem of course is that they can be incredibly flat when done wrong. I really try to avoid using skill challenges that are likely to only require 1 or 2 characters to succeed unless the sc is part of a combat encounter.
I think the trick to sc's is to not only get everyone involved (assuming a non-combat sc) but to also make the challenge meaningful without causing the game to grind to a halt if there's a failure.
I think the best SC I've designed so far involved the party attempting to talk to the spirit of a former guardian of the major artifact in the campaign. The individual in life belonged to an organization dedicated to protecting the secret of the artifact (think Last Crusade). In order to get the needed info from the spirit the party had to a) disable the protective runes around the coffin (3 successes), b) open the locks on the coffin to release the spirit (3 successes) and c) convince the spirit that the PCs were friendly and had the same goals as the spirit (4 successes).
The runes required arcana checks, the locks Thievery, and the convincing could be done by a combination of Diplomacy, Bluff and Intimidate. History, Religion and Streetwise were available as secondary skills that could provide bonuses to primary skills and of course, I was always willing to let party make other suggestions if they could properly describe the use of the skill.
Success meant the spirit came out and talked to them, giving them the info they wanted. Failure meant that the spirit summoned a host of undead guardians to repel the intruders but if the party defeated them, they could then negotiate with the spirit. No additional XP would be given for fighting the baddies (in other words, no incentive to fail the challenge). If, after the fight the party still failed to convince the spirit, then they would have to look elsewhere for the info.
Unfortunately, in play, the artificer rolled 1, 1, 2 on his arcana checks, causing the challenge to fail almost immediately. After the fight though the party succesfully negotiated with the spirit and received the info they needed.
As for SC's I've seen, there was a really good one in the final encounter of Radiant Vessel of Thessk an RPGA module. Basically, during the fight one or more of the party members needs to help deliver a baby. I was also a player in a game wherein the party was tasked with chasing a harpy at night. We had to make athletics checks to stay on the horse, perception checks to see the harpy and obstacles in our way and nature checks to help navigate, etc. It worked pretty well aside from the fact that on the last check we failed the challenge. In this case, the harpy got away causing the adventure to progress in a different direction rather than just grinding to a halt.
Unfortunately, I've also seen plenty of challenges fall flat either because only 1 or 2 people participated or there wasn't enough variety or description of what was going on, etc. I do really like the suggestion above for social challenges in that the number of people who need to be convinced determines the complexity of the challenge. Rolling Bluff and Diplomacy over and over again in order to convince the duke gets old fast.