My internal guidelines for DCs in 4E is also to consider what "level" the challenge should be. Just as you have an effective encounter level based on numbers and levels of monsters. So a 8th level group doesn't necessarily get a 8th level skill challenge, just like it won't always get a 8th level combat encounter.
Makes sense.
One of the biggest challenges using 3E is that there is a far wider gap between "untrained and bad ability score for skill" and "maximally trained, with feat, synergies and magic items". This makes it hard to predict which DCs will actually seem as a challenge, and which DCs will simply be too hard, and which players can actually contribute to a challenge.
Agreed. I would suggest that a 3.5e DM needs to be more liberal in which skills to allow for the challenge than does a 4e DM. (I would also argue that the Skill Challenge rules from the 4e DMG are also rather too restrictive, but that's another debate for another day.)
Of course, I'm also in the camp that suggests that PCs should really be diversifying their skills (across the group; I'm not suggesting that a PC should put just a few ranks in a lot of skills). So, there should be
someone with Knowledge(arcana), Knowledge(architecture), and so on... Though that's not always easy when you only have 2 skill points and a narrow set of class skills.
I guess one way to deal with this is to provide a wide range of possible DCs. One of the very low DCs might just be suitable to get a support. One of the really high DCs might get you extra successes, secondary benefits, negate failures or similar things.
I like this.
To ensure that a single person with the best skill modifier is not the only one participating in the challenge, introduce aspects where mutliple members of the party have to contribute.
One concept found in some published 4E skill challenges is the "group check".
I like this as well. I certainly take the view that in almost all Skill Challenges, every PC who is present must at least try to contribute - if they just do nothing then I chalk that up as an automatic failure.
(I'm sometimes quite evil like that.

)
Another way might be to have "prerequisite" checks. Maybe you can attempt a Diplomacy Check only after someone else succeeded his Knowledge (History) Check unveiling a certian fact. The latter check might be easier or it might just be that the Wizard can do it but the Silver Tongued Rogue probably can't. The check doesn't actually grant a success (or failure), but it opens a new way to gain successes and failures.
And another good idea.
Some more stuff I've been considering for Skill Challenges:
"Spine Skills": As I said above, I'm very liberal in tying skills to Challenges. If a player can come up with a justification (no matter how tenuous, mostly), I'm inclined to allow it. However, there are some Challenges that just have to be tied to certain skills. If you're climbing a mountain, then Knowledge(nature) and Survival will obviously help, and other skills may well apply too... but eventually you're going to have to make a Climb check or two in there as well.
And so I have the "Spine Skills", the skills that cannot be avoided to pass the Challenge. Basically, in order to succeed in the Challenge, the party must not only get the required X successes, but they must also get at least 1 in each of the "spine" skills, and half of their total successes must also be in "spine skills".
(So, in the "Build a Cathedral" example, it is likely that Knowledge(architecture) and Craft(building) would be spine skills. Intimidate or Diplomacy would help motivate the workforce, Profession(merchant) would help get the materials, and Gather Information might help track down hard-to-find items... but eventually, someone is going to have to actually build the thing!)
First Past the Post: Some Challenges don't really have a notion of 'failure' - all that matters is that you get there before the other guy. In that case, I would have each 'cycle' of rolls represent a block of time (or monetary resources, or both), and count the number of 'cycles' until the target is reached.
(Obviously, this is good for a race scenario. If it's just a matter of time and there are no real consequences of taking longer, I would probably just say, "two weeks later, you're done..." and leave it at that.)
The Deadline: Similar to the above, except that there is a pre-established number of 'cycles' allowed before the Challenge is declared a failure. Perhaps each 'cycle' represents a week of work, and if you're not done within four weeks then the contract gets cancelled.
The Filibuster: Conversely, sometimes it's not really a question of success, but rather how long you can keep going before you fail. In this case, I would have each 'cycle' of rolls represents a block of time, and count the number of 'cycles' before the 3 failures are recorded.
(This would be good for creating a distraction while another group get away, or for delaying the movement of troops or materiel, or similar.)
Phased Challenges: Sometimes, the conditions of a Challenge adjust as time passes. Strictly speaking, the construction of a cathedral should be a good example of this: you first draw up plans, hire a workforce, and gather materials, and
then build the thing.
This can either be modelled by chaining several smaller Challenges together (having success in one provide a bonus in the next), or by using a Group Check for each phase, and emphasising different skills in each.
Interrupted Challenges: This one has the Skill Challenge pausing at certain points to break up the action - possibly allowing the PCs to influence the ongoing Skill Challenge. Basically, you assign a condition and then design an event to go with it.
For example, when building the Cathedral, if the PCs hit 2 failures, the (NPC) foreman comes to them and says that they've been losing a lot of workers due to attacks from the sewers. The men won't do any more work until something is done. (The PCs then investigate, find a nest of wererats, and wipe them out.)
Success in the keyed event could either give a bonus to the next 'cycle' of rolls (weak), grant one or more automatic successes (moderate), or even negate a failure already recorded (more powerful). Failure might have the opposite effect... or might have no effect at all - it might be enough of a punishment that the PCs didn't get the "success" reward.
It's probably worth noting that I don't have the DMG2. I
do have Galaxy of Intrigue (SWSE), but I haven't had a chance to do more than glance at it - it certainly seems to add a lot more to Skill Challenges than was present in DMG1, and may cover some or all of what I've just outlined.