My understanding of the Phoca Gallery Menu Module is that it uses the sorting order you've maintained in the Categories maintenance.
I'm using the little arrow to the left of the Title column to sort all my categories in Ascending order (I assume it is supposed to do this alphabetically):

I'm getting some weird sorting at Level 3 though. For example, under the colour Grey (2nd level), the category "Tinybot" should definitely come after "3M" and "Avery Dennison". For some reason though it is always placing it before 3M. I know it I can manually move it, but then when I want to resort my categories, it will get moved again. I've looked and there are no additional spaces or characters in the category Tinybot. Any idea what could be causing this?

Cheers,
Lee