In the end, it seemed that this problem was being caused by the menu being too large.
It was working fine (PHP settings had been adjusted to cater for the size of the menu), but then broke, and no amount of tweaking PHP settings would allow the full menu to run.
The solution was to break the menu into segments, and use UberMenus ‘Menu Segment’ function to piece it back together.
Thanks for your support, X Team.