I'm finally back with something, even if it's not really a solution. I mailed the Galaxy dev list but I got no answer so this is the only way I could find to have LEfSe working on a local Galaxy instance.
I remove the Galaxy version that was installed following the tutorial (using git clone command) and installed a previous version found on this page :
https://github.com/galaxyproject/galaxy/releasesThe v14.02 makes LEfSe run correctly. Maybe more recent versions also work, I had to go back to this one because of openSSLv3 errors during install of others Galaxy versions, which are due to the Debian environment I'm using.
To install, just decompress the archive and run galaxy-14.02/run.sh
Also, it seems that trying to keep the tools previously installed in a more recent Galaxy isn't working. I got errors testing them, which were solved when I made a fresh install from the tool shed.
Hope this could help someone.