It's really hard to do what you did in java. Just the code for the window and keyboard input will probably consume about 512bytes. I remember there was a contest before, called java4k, although it's pretty much dead now, I tried to get some source codes of the games they used to create for that contest and I found 1 guy from who I learnt about "pack200". So using proguard + pack200 I managed to make 1.99 KB.
What is interesting is that Notch (creator of minecraft) managed to do Meg4kman in under 4KB. I don't know how he did it considering that it has enemies and 25 levels, it's pretty much a bigger project than this one. It's amazing!