I finally figured out how to get Java installed with Kubuntu. Some nice people at ubuntu bakcports packaged both j2re 1.5 and j2sdk 1.5. Kub is based on Horaey so you simply need to add horaey related entries to your /etc/apt/sources.list:
deb http://ubuntu-backports.mirrormax.net/ hoary-backports main universe multiverse restricted
deb http://ubuntu-backports.mirrormax.net/ hoary-extras main universe multiverse restricted
Then just install them using apt:
apt-get install sun-j2re.15
apt-get install sun-j2sdk1.5
Please note that the whole operation takes a while. The packages are 38MB and 65MB each :P
So there. Java on kubuntu without problems.