I am surprised we haven't had a european-fantasy-themed animated show yet, save for the short run of a Conan series I never got to see. You'd think there would be enough appeal and demand for it, given the apparent popularity of midieval themes for toys. Legos, Heroscape, several fantasy-themed boardgames... all would seem to point to enough interest that a TV show of some type would make sense.
I think a realistic thin-line anime style would be good, something like you saw in Witch Hunter Robin. I could live with the Clone Wars style, depending on the character designs; it's not my favorite but I've seen far worse. Hey, it could be in Rugrats style.
I think it would be great to re-do part of the original series but in a realistic style with modern sensibilities. Needless to say, it would be in Adult Swim territory. Do away with some of the corny names (Presto, I'm looking at you), make Uni a parasitic shapeshifter sent by Venger, and give the mage some awesome freaking magical abilities. (That was my main beef with the show, was that the mage had to be such a wimp because God forbid we show kids that magic could have really powerful effects).
But the best bet would be to make a clean break with the past and have a core adventuring party. Not the iconics, either. Fighter, cleric, mage, rogue, then maybe a ranger or monk.