Galaxy tools are installed from the Galaxy interface, the toolshed interface is for managing and creating tools, i.e. for tool authors.
Galaxy does not automatically install dependencies of all tools shipped with it, you can use the admin panel’s option ‘manage dependencies’ to install them.
The tool you are trying to use has not been updated since 2013, it also has no bioconda package. That is probably why it does not install properly, and maybe it never did.
I recommend finding a more modern alternative depending on what you are trying to do (fastqgroomer comes to mind).