Generally, an ideal skill challenge is one that is more complex than just "Convince the Duke to help you." Anything that can be narrowed down to a single Diplomacy check doesn't need to be represented as a skill challenge.
The goal of a skill challenge, ultimately, is to present a complex non-combat challenge in which all PCs can participate. Ideally, it functions hand in hand with roleplaying and creativity - the DM uses the framework of the skill challenge behind the scenes to help resolve the various ideas the players come up with.
Now, why would you want such a thing? As mentioned above, to help provide opportunities for all characters to be involved in the scene - rather than just having the bard, as usual, roll Diplomacy checks until the Duke agrees to whatever he wants.
Secondly, it gives the DM some guidance on how challenging to make the encounter (and, thus, what sort of rewards are reasonable to offer for it.) This avoids having to simply use DM fiat to decide that, "Sure, setting fire to that shed sounds like a good distraction, so it works and you draw off the orcs." Instead, the DM has some guidelines on how to actually see if the party pulls this off successfully.
To go back to the negotiation - sitting around a table rolling Diplomacy checks isn't a good skill challenge. (And using something close to that in the DMG was a bad call.) Instead, the skill challenge probably starts much earlier - the PCs arrive in town, and know they will need to meet with the Duke and convince him to help them with the upcoming orc invasion.
The party is told they have an audience with the duke that evening, and can present their requests to him then. They are, perhaps, warned that he doesn't help adventurers willy-nilly, and they may be well-served spending their time making sure they have prepared a persuasive argument.
At this point the dwarven fighter and halfling rogue might hit the streets, looking for info on the current mood of the town. Chatting with some shady pottery merchants, the rogue learns (via a Streetwise check) that the Duke's men have a favorite tavern in town. They hit the bar, and the dwarf engages the Duke's captain of the guard in a drinking contest (via an Endurance check), and by the end of it, finds out that the guards have little to do and fear their skills will grow rusty.
Meanwhile, the elven wizard visits the town library to learn more about the history of the duchy, the wars it has fought in, the lineage of the Duke himself.... etc.
By the time the audience comes, the party has a number of convincing arguments at hand (the army is ready for action, this is a threat the duchy has fought off before, etc), and during the evening they will present their arguments and make appropriate social checks to deliver them well.
That is more the goal of a skill challenge - not something to handle with a single Diplomacy check, but instead the framework for an entire scene and various opportunities for everyone to participate.
Now, why use it instead of just handling it all freeform? Again, mainly just to help give the DM guidance on directing how the scene goes. He knows that if the dwarf embarasses himself when drinking the guards, word will get back to the Duke and hinder the party's chances but not ruin it (1 failure). Whereas without the guidelines, the DM pretty much needs to arbitrarily decide the outcome of each event without any context. How much impact does the drinking have on the audience? How much info is in the library and what relevant info can be found in an afternoon? Etc.
Skill Challenges certainly aren't a necessity to running a game, but they are a useful tool. And the goal, at least, is for PCs to be deciding actions and roleplaying what they do... which is then resolved by appropriate checks. A group that just goes around the table and declares skills and rolls for them might be an unfortunate result of how some skill challenges are run (and can even work for some groups), but is not the real intent of the system.
