So, In this new world, are they humans? And do these humans speak... what? English? expalin that first, and you will have no problem with the names.
Otherwise, figure out what language do the speak, and that should give you the basis for the names. Different language have differnet story, different common sounds, etc... The names of the places are probably in the native language or some older variant.
It is not rare that people base the names in combinations of words, names of places or objects. The etymology of names doens't have to be strict, but it makes sense that common names have some meaning the culture where they are from.
You will probably solve this if you solve the story of the new world. How is it that there are humans there? From where and at what point of the history thay got there? That should give you the basic language to work with.
If there are not humans, you proably should start looking into creating a new language "from scratch". For that you should - again - consider the culture of the new world, but also consider their morphology, maybe some sounds are esier for them - and some that are possible for us, are imposible for them.