Speaking of fleshing things out, what exactly would constitute a good storyline? Your typical Zelda storyline seems to work well at first glance, but it’s just not intricate enough when you consider that a massive portion of Zelda games is spent dungeon crawling; it’s part of what makes the Zelda series what it is. This is an inherent problem when adapting nearly any video game to the big screen; what makes video games so long is usually one or more of a motley crew of gameplay-extending devices: mini-games, dungeons, and fetch quests, just to name a few. With the exception of the Metal Gear Solid series, nearly no story plucked directly from a video game would work out well in theaters.
Generally what happens from there is that a more generic Hollywood story is adapted to include elements from the game (for a crash course in this, watch pretty much anything by Uwe Boll). One has to wonder if this could possibly be a respectful treatment for a game series as revered as Zelda, but when you get down to the essentials, video games and movies are two incredibly different media in regards to what is acceptable or not. Zelda really is better attuned to a TV series, where each episode could represent the obtaining of a new Awesome Item, which is generally how the Zelda series works out. Video games can be digested in smaller chunks, but you have to watch a movie all at once.
Thus a movie is a bit more tricky business, but could it be possible to bring Zelda’s sort of "fetch quest" style of story to the big screen? I think it’s definitely possible, but the pace needs a severe adjustment. If Link went straight from one temple to another, it’d get old fast, but if things were mixed up a bit it could possibly work out; a good example of this can actually be seen in Pokemon: the Movie 2000, wherein the plot consists generally of a fetch quest, but with other events keeping the whole idea from growing stale (I’m sure there are better examples, but this one worked out for me). Twilight Princess seems to have this idea down cold; during the first half of the game, you’ve got to do the same set of things three times, but it feels so NOT monotonous I could barely believe I was playing a Zelda game.