When they said it had gotten too complex, I interpreted that to mean that there was too much extraneous bullshit that they felt they needed to explain. Too many collectibles, so that it was no longer feasible to expect the player to remember what each one does - hence telling you what every one of them is when you pick them up. Too much distance between destinations, so your sidekick keeps telling you where you're going and why. Too many stock puzzle elements that only do one thing, so that every time they show up they give a brief primer so you're not sitting there trying to remember what that particular geegaw does.
The remedy to that kind of complexity is streamlining: Just a few basic kinds of resource, with multiple uses. A re-tuning of the storyline and overworld, so that the challenge is not "where am I going" but "how do I get there." A few kinds of general puzzle element that interact in complex ways. With a reduced need for making sure the player actually knows how to play, more gameplay value can be found in demanding the player play well, which recent games have shown that Nintendo hasn't yet forgotten how to do.
I see nothing but good things coming from that perspective, provided that's what they meant by complexity. And I'm fairly confident it is; the other kind of complexity hasn't increased in half the series' length.
