I think some of the ideas here are very good, some of which are what I was thinking so I won;t reiterate them. However pay close attention to an element that often gets short shrift....
Naming Conventions - The type of names used on the world either in an overall way or culture by culture (this is what I recommend). Also, the names you, as setting creator, use for the naming of nations, peoples, fortresses, forests, etc. are very important. Fantasy is full of good concepts backed dumb or incongruous names that just scream that no thought was given to this aspect of design.
Solid, right sounding names add a lot to the versimillitude of a setting. If your setting is celtic inspires find some celtic names and tweak them a bit if necessary so they have the sound you want. Use a name generator program to help if you need to.
Avoid cliches...Mount Doom, The Elf Forest, The Dark Dungeon....in other worlds cheesy crap names. However, you may have people colloquially call a forest the Elf Forest, that's fine but use its "proper name" when referring to it most often...Maybe calling the forest Irthyl Valar which might mean, in the elven tongue of your setting the Elven Wood. The local humans may call it that but refer to it by its elven name to give it personality.
Names for people can be culturally based or purely fantasy. Fantasy names like Laurana, Tanthalis, Ariakas, Kitiara, Caramon, etc. are well thought out, good sounding names to the ear. Judging fantasy names is hard but they will sound right intuitively and will not sound like you named the NPC as an afterthought. The benefit of culturally valid names is that they ring true do to linguistics that fantasy names can't have.
Also, if you choose alien or very odd sounding names be consistant across a culture or the entire setting. Athas, Tekumel, and the new Violet Dawn setting have an "alien" and non-traditional quality to their fantasy and their naming conventions are consistantly different but that consistancy leads to a distinct personality.
On the other hand, having two guys in the same culture with one named John the Giantslayer and the other names Illori Dak'thul just IMO indicates that the designer had no idea of the personality of the setting he was trying to create. Or he was just really lazy.
Just a couple thoughts.
Chris