I remember in an interview years ago that Shiggy said they'd started on "the next Zelda" in 1997 (which turned out to be MM). TWW probably didn't start until 2000 or very late 1999, and the graphics weren't finalized until late 2000 or early 2001. I think they knew exactly all the hate which went on for TWW's graphics, and began to change from late 2002. Also, it's possible Nintendo had several graphic types readily available before they went with TWW. This new Zelda could have been a standby just in case.
Anyway, as TWW production was winding down probably October or November, I imagine this next Zelda was in the planning stages for a bit.
Hell, Super Mario 128 was supposedly in development while Super Mario Sunshine was, right?