I suppose I'm fine either way as there's pro's and con's to both styles.
For starters, I'm not even sure the previous overhead style was going for a "puzzle" style to begin with. More like the oldschool 2D Zelda games like ALttP. At least, I don't remember there being any plans for puzzles at least, and there weren't puzzles in the demo. But the animations were pretty good and much more involved than HotB, for what little we saw. There was potential there, at least.
But on the other hand, sidescrolling is what he's used to and what we're used to. So chances are it won't be in development hell like it has been for the past year.