You are maybe using something in your Java code that can not work on a headless system, such as graphics components (Swing objects, images, etc.). Some of these components, instead of being directly handled by Java, are handled by underlying platform (Windows kernel itself or X-Window server on Unix). This way the overall performance of application is boosted.
So the question now is, ok if it was working on Java 1.4, why doesn't it work on 1.5? My bet, given the peformance boost since Java 1.2 that Swing has received over time, is that Sun has moved the management of some graphic objets to OS level to increase performance. So if you can not stick to 1.4, then you should revise your code.
This good article will help you understand how to modify your application to make it headless-friendly.