As a quick update I can confirm this also works with the new 4.3.0 version of x-cart. The new version does include a few extra choices with the Fancy Categories module being included, but it still doesn't do a "normal" functional menu. I've just followed my own post from the first page and it works fine, all sorting on sub-menus is correct as well
*EDIT*
Sorting wasn't correct! It just happened to be correct because it was in alphabetic order anyway!
Code should be as per Victors Code on post 16:
http://forum.x-cart.com/showpost.php?p=253759&postcount=16