Primary Social skills: Bluff, Diplomacy, Intimidate
To detect the target's reactions: Insight
To impress someone with physical ability: Acrobatics, Athletics, Endurance
To raise a pertinent fact: Arcana, Dungeoneering, Heal, History, Nature, Religion, Streetwise
So, 14 skills that could conceivably be used by someone in a social situation. More than enough to support robust skill challenges.
However, it looks like the system might fall down for other situations.
THIEVERY Skill Challenges
The TRAPS preview example gives a skill challenge using only Thievery. Roll 4 successes before you roll two failures? Where's the fun in that? What other skills could you include in a trap skill challenge? Acrobatics for some larger traps, I guess. Endurance for underwater traps? Perception, maybe? But, it's not nearly as robust as the social situation.
CHASE Skill Challenges
This one seems doable. Seems like the following skills would be usable:
Acrobatics, Athletics, Endurance, Stealth - for obvious reasons
Bluff - to trick the opponent into going the wrong direction
Dungeoneering, Streetwise, Nature - to use the surroundings to aid in your escape
Perception - to notice a shortcut, etc.
WILDERNESS TRAVEL Skill Challenges
Seems like skill challenges would be good for finding your way in the wilderness. Each success gets you x miles closer, while every failure gets you y miles further away. Skills you could use:
Athletics, Acrobatics, Endurance - to use a shortcut across some difficult ravine, river, etc.
History - to recall a legendary path through the mountains
Nature - to find the best route through the forest
Perception - to notice the deer trail
SEARCH A ROOM Skill Challenge
Are there enough skills to enable this? For every X successes you get before you get Y failures, find one hidden item. This could simulate the inability of the PCs to think of any more places to search for things.
Arcana - to remember that wizards often put important things out of reach of familiars
Athletics/Acrobatics - to wriggle your way through some rubble to find the stash
Dungeoneeing - to realize that crack in the wall could easily expand into a large, hidden cache
History - to remember that the ancient Knights of Kelliark often placed valuables in their helmet visors.
Insight - to survey a room, extrapolate the personality of the inhabitant, and then deduce where they might like to hide things
Nature - to realize that mold shouldn't be there, maybe something is damp behind that wall
Perception - obviously
Religion - to know there are always 4 miniature holy censers, not just 3 like you have found
Thievery - obviously