Java performance weirdness

So I'm writing this game in Java. Just a simple rectangle moved with the arrow keys. Added a FPS counter. Then comes the weird part.
On Java 6 update 19 and 20 the game is two times slower than on the (quite old) Java 6 update 3.
Tested on AMD and Intel CPU's. On Windows XP.
And Java 6 update 10 should have brought quite a performance boost. I don't get it.

Asked a question on stackoverflow. I hope somebody has an answer.