Ubuntu has the option to install a headless Java — this means without graphics libraries. This wasn’t always the case, but I encountered this while trying to run a Java text editor on 10.10 the other day. Run the following command to install a JDK that has these libraries:
sudo apt-get install openjdk-6-jdk
EDIT: Actually, looking at my config, you might need the JRE. If that’s the case, run:
sudo apt-get install openjdk-6-jre