If change is to be made to the dungeons, I think it needs to step away from the various elemental themes. Simply choosing different elements will get old, and in the end, it's still the same as before.. just with different elements.
I think a great way of bringing about change would be focusing on older elements- specifically, items obtained in the dungeons. In older games, you'd obtain the item and use it not only in that dungeon, but also in the ones to come. This has been disappearing from Zelda, and I think a great way of bringing it back would be by changing the dungeon types. Example:
Say in one dungeon the theme is accuracy. Say you already have the bow by the time you reach this dungeon, and in it, you obtain the hookshot. Two classic items that should always be in Zelda. Or make it a double claw shot like in TP. So, a great thing that could be done would to implement the floor-changing function found in games like MM and LA and ALttP. Change the floor, something moves, you have to shoot a target or switch with your arrow spot on (accuracy). This moves something else, you must accurately grapple an item to move to the next spot and quickly and accurately shoot the next target or switch before a timer runs out. It'd all fall on your accuracy. It'd bring about change, it'd bring back item usefulness, and it'd work great with Wii Motion Plus.
Other themes might be strength or speed- figure the Phantom Ganon fight where you have to hit the ball of energy back. Wouldn't it be neat if it actually got pretty fast? The Wii Motion Plus can gauge how fast and how hard you're swinging the controller.
I think something like the above would be great changes to the first three dungeons. For the others, I think putting less focus on elemental themes would be just as good. Perhaps making one level a true labyrinth would be cool (and possibly frustrating). Something mind-boggling like MM's Stone Tower needs to be implemented to make things feel a little more unique.