Actually, my own game uses this kind of location mechanics, essentially a space game where you explore star-systems, with each system composed of a number of planets, and these having cities, and locations in the cities. Players are free to room about, and I currently already have about 8-10 planets (its a WIP but already quite extensive…). I have combat systems (ship-to-ship, character-to-character, etc).
The main issues I have encountered so far is that some people can complain of a feeling of being lost in the game (given so many options of where to go, where do you start?), so you may find that you need to implement some features to give a sense of direction (I implemented a second officer you can ask for advice, which is a rather complex script which results in different advice being given based on what the player has done so far).
Essentially, the problem is that most people who play CoG are used to “rather linear” plots, where your choice dictates incremental changes to the storyline. But, you don’t have to choose the path of the story, which will never end up in a loop (i.e. the story will conclude somehow, if you continue making choices). In a game like mine, or like the one you have in mind, the character can end up 5 times in the same cavern, wondering what he has missed and how to go forward. Many gamers in other genres might be used to that feeling, but those in CoGs don’t necessarily want such games, so you have to be a bit careful. I also have implemented a timer, to force some movement into the game, but you will find also that this game slowly and rapidly grows in complexity, an issue I am currently struggling with…