Eclipse is supposed to be the best overall, but it has been called "too complicated for its own good" on more than one occasion. The free Borland JBuilder is fairly good, but it once apparently decided to delete all of the .java files in one of my project (I had a backup, though) so I'm not really sure about its stability. Overall Java IDE's are pretty weak on Linux. If Windows is an option go with JCreator, but from the sounds of it Windows isn't an option.
-------
Hallmark®: Your home for overpriced cardboard rectangles.