I'm assuming that you're using the program after getting from the main website rather than the Ubuntu repository. Okay timidity doesn't work. You'd have to install libtritonus-java and libtritonus-bin and Sun Java version sun-java6-bin from Synaptic Package Manager or type the following in a command line:
This worked for me. Also, after you're done, you can optionally add some soundbank from the Java Sound API and install them as instructed in the readme file that comes alongwith. Remember that since we're using Ubuntu, the <install-dir> would be /usr/lib/jvm/java-6-sun/.
sudo apt-get install libtritonus-java sun-java6-bin
I hope it works for you as well.