I think it would be easier for you if you’d stick with the old menu output and used css to emulate your submenu columns. You can left-float the elements in your submenu (while giving them an appropriate with – e.g. 33% for 3 columns), which sorts them horizontally rather than vertically, but otherwise will give you a column-like effect.
