While the skills in d20 Advanced cover most situations, you may wish to add a new skill to the game for different reasons.
First, a new skill may combine tasks normally handled by two or more different skills under a single heading, allowing characters to be skilled solely in that aspect without any training or ability in the other skills. Second, a new skill may be useful with certain rules options or new systems (including those detailed in this book). Lastly, a new skill can provide additional detail or may be important in a particular sub-genre or style of campaign.
When should you create a new skill and when should you create a new use for an existing skill? It's largely a matter of taste. Generally, adding a new use to a skill is easier in terms of game structure and balance; you don't have to worry about adding another skill to existing characters who ought to have it, or retroactively redesigning any characters to fit the new skill. Instead, it just becomes a less-often used aspect of an existing skill. It's easier to integrate new uses for skills into an ongoing game than it is to add new skills.
If you want to create a new use for an existing skill, but don't necessarily want everyone trained in that skill to have access to it, you can create a feat that grants access. This is a good middle ground between creating a new skill and a new use for an existing skill, plus it becomes something characters lacking the feat can still do occasionally, if they’re willing to spend a hero die to emulate the feat.
Another middle-ground option is the Skill Challenge system section of this chapter, which allows certain "advanced" uses of skills at a penalty to the skill check or Difficulty Class. This ties in with the previously mentioned feat option if there are also feats for performing certain skill challenges without penalty.
Still, there may be cases when you want to create an entirely new skill. This is especially so for esoteric or unusual skills that don't match up with any existing skill and aren't suitable as new aspects of a skill, even with an enabling feat. You might be setting a game in an era where existing skills wouldn't be as applicable (such as the Technology skill in medieval times). In this case, there are a few things to keep in mind. You should try to keep the number and utility of each of the skills available to a given ability score roughly in-tact. Too many skills in one ability makes it too attractive, and too few makes players more likely to use it as a "dump stat" and avoid investing points in it.
Think of ways to translate the utility of an existing skill to a new one if you mean to replace it. For example, for a fantasy game, the Science and Technology skills probably aren't as useful or genre-appropriate. These two skills are knowledge-heavy and have numerous craft applications. Technology in particular gives you more options for interacting with technological devices. So to translate these concepts to a more fantasy game, you might consider recasting them as Alchemy and Magical Items, with Alchemy being focused on brewing potions and analyzing spell components, while Magic Items would allow a character to build and use magical Devices.
If you choose to create new skills from the ground up, keep in mind that most skills have about four or five specific applications, and are generally broad enough to apply to other unforeseen circumstances too. Apply the skills to an appropriate ability score and you're good to go.