Whenever setting up a Linux distro, especially a Debian derived one (like, I don't know, Ubuntu), always, always, always make sure that Sun's JDK is the selected Java implementation and NOT GCJ. Here is the quick 'n easy command in Ubuntu:

sudo update-alternatives --config java

Frankly, I think I feel a rant coming on. Maybe this has already been fixed in a later edition of Ubuntu (I wouldn't know, as I am still at 8.04 for power management; yes, this is both a hint and a gripe: I want PM to work at least as well on my machine in current releases as it does in the current one), but Sun's OpenJDK should be the default. It is almost 100% of the closed source JDK, with the last bit coming along soon, fully GPL'd (so no licensing complaints), and much better than GCJ for run of the mill Java applications.