As a skill challenge this is my structure:
I agree. It's possible to make a decent skill challenge but it always seems like it takes more effort than it's worth. Sure, "convince the king" makes a lousy skill challenge. So do a lot of other things. But many of them SEEM like skill challenges so DMs try them.
But even given the skill challenge you presented, what makes a skill challenge better than simply a series of skill checks with no defined number of successes? You could run the skill challenge instead as a series of rolls based on the situation at the time. Which means after a couple of failures, they might find themselves in a bad situation and need to make more skill checks to get out of it, but they technically haven't "failed" yet. Even though the skill challenge rules would say "two failures and you're out".
On a mostly unrelated note, my favorite Skill Challenge story was when a friend of mine tried to invent his first skill challenge. It was fairly complicated, though I don't know the exact number. The skill challenge was "Build a bridge so that the cart we were guarding could make it across the ravine since the old bridge was out."
Everyone saw the bridge out and immediately told the caravan master that he was screwed and there's no way he'd get his cart across. The caravan master spent forever telling us we weren't getting paid unless we got him across there. We told him it was impossible as we'd need weeks and some skilled artisans in order to build a bridge. The caravan master said he needed to be there later today. We said it was impossible. The DM stepped out of character in order to tell us that we were in a forest and bridges were made of wood, so it should be possible.
We all shrugged and said "Well, we don't know anything about building bridges, but the DM says it's possible so...I guess we build a bridge. How exactly do we do that?"
The DM starts miming chopping down a tree with an axe and sits there waiting for someone to pick up a dice and roll.
I say, "We don't even have anything to cut down trees. We have swords, which don't exactly work for that purpose."
The DM said "Umm...err....well, you have an axe, right?"
I said, "Yeah, a battle axe...which is quite a bit different from a wood chopping axe."
The DM said "Well, that'll work."
I say "Alright, I'll cut down a tree then...I suppose."
He says "So, what skill do you think you'd use for cutting down trees?"
I say, "Umm, Athletics maybe?"
He says "Great! Make a roll."
Then I succeed and say "Alright, then...we do whatever we need to do to turn this log into a bridge."
He says, "Well, what skill do you think would be useful in this situation?"
It isn't until now that I realize the DM has turned building the bridge into a skill challenge and hasn't thought it through at all. He simply wrote down 10 successes before 2 failures, Athletics, Acrobatics, and Endurance are the primary skills. He was simply waiting for us to keep announcing skills and rolling them without really knowing or caring what they were for as long as we got 10 successes.