When Confluence.atlassian.com was upgraded to 3.2-beta2 from 3.1.1 (or 2?) the Velocity Helper plugin module was disabled. This prevented the tree from showing. This also happened on qa-cac, so presumably it's not a once-off and may happen to other customers.
Turning on the Velocity Helper from the plugins administration screen works and makes the tree work. I'm yet to establish why this occurred or whether this will reoccur on a restart.
A possible scenario is that this happens whenever we go from non-bundled doc theme to bundled doc theme.