I vote Perl. To toot my own horn along with Perl's, see some examples of
what you can do at falkow.stanford.edu/whatwedo/software.
Bioperl is ahead of Biojava. Packaging executables for PCs is simple
using ActiveState's tools.
I think that if I were making the decision, I would mostly be considering
whether time-to-finished-program or cross-platform compatability is more
important. Perl will be faster to get a working program, but Java
will be better for making Mac software available. Perl works fine on
Macs, but Tk (for the GUI) is a little trickier to get working.
My 2 cents, with the caveat that I have only limited experience with Java.