The advice is true for all public Galaxy servers presenting with problems not supported by the core team (Main:
http://usegalaxy.org and Test:
https://test.galaxyproject.org). Just keep in mind that "Test" really is a test server. Various errors at unpredictable times should be expected - meaning, it is best to not use Test for critical work.
Should you be using the version of the tool from the Main Tool Shed (
http://usegalaxy.org/toolshed) in a local or cloud Galaxy, contact the administrator of that instance. If this is a server that you run yourself, I can let you know that the error tends to be related to high server load and/or insufficient resources. Often it will go away after a few minutes if the issue really is peak database-load. Has the tool ever run successfully on your server? If not, consider moving to a PostgreSQL database if you have not already (instead of the default SLQlite). If the tool will run line-command with the available resources, it should almost certainly run in Galaxy with the correct configuration. Just in case you need it, these are the production database set up instructions. More is in the Admin hub of the wiki.
http://wiki.galaxyproject.org/Admin/Config/Performance/ProductionServer#Switching_to_a_database_server