Just wear leather hiking/work boots and claim the Leatherman is for fixing various clothing items you are wearing as they need. All you need to do is justify you are carrying it for a non combatant/stabby purpose. Just don't be stupid and carry the kit into restricted areas, like airports, on public transport or around schools etc... Unless your job requires you need the tool in those areas. As a GA pilot who is approved for pilot maintenance there is no problem carrying such a tool airside. Airlines will say otherwise as they don't want you chopping things on the aircraft, that being said a leatherman would have been useful on several occasions where we were almost grounded due to lockers jamming shut, and various other not really airworthiness things where a tool would help pry/cut open something. In those cases I was able to use my jail skills to create makeshift pointy things to do the same from readily available stuff. I guess the laws don't realize that criminals can be resourceful as well, after all they still manage to procure weapons and kill each other in the lockup. I'm surprised that Queensland hasn't banned coat hangers in public to cut down on car theft...
PS I have no issue with knife laws that stop kids (or anyone else) from carrying blades for the obvious use of harm to others. I can only assume that the police officer possibly thought you were holstering a flick knife or similar and not a pocket utility knife, and over reacted. But reality is someone could (and will) carry something else pointy for the same reasons, and you can't ban everything...or can you?