Currently, Ubuntu comes with GNU Java (gcj/gij) installed as the default Java. (I'm not sure but I think it is because OpenOffice needs Java).
Unfortunately, this is a very slow and incomplete version of Java 1.4, which does not run many Java programs very well. Because of this, many users get in trouble when they want to use some Java programs - they don't work well and run very slowly. The solution is to install a better Java, such as Sun Java 6. Sun Java 6 is not 100% free and open source software (yet), so it cannot be installed as the default Java with Ubuntu.
There is, however, a much better free alternative implementation of Java than gcj/gij, IcedTea:
http://icedtea.classpath.org/
IcedTea is based on the source code of Sun's Java, with the non-free components replaced by open source alternatives.
Proposal: Instead of the obsolete gcj/gij, install IcedTea instead as the default Java. (Fedora 8 does this already).
Developer comments
OpenJDK is now the default Java for Intrepid