Seems like you might be experience flickering. What are you drawing on? A Canvas? A Frame? A JFrame? A JPanel?
IIRC AWT descendants don't double buffer automatically which causes flickering if you don't do it yourself and swing thingies (JFrame, JPanel) do double buffer but they handle their painting a bit mysteriously from you - in that case, you might want to turn swings automatic painting off ( "setIgnoreRepaint(true);" ) and paint manually by calling it inside your game loop and also implement your own double buffering like with the AWT descendants to get rid of flickering.
Here's a good link I found with google-fu that explains a bit more in depth http://stackoverflow.com/questions/4430356/java-how-to-do-double-buffering-in-swing?answertab=votes#tab-top
Flickering is basically what happens if you try and show an image to the screen while the image hasn't been fully drawn yet. So what Double Buffering means is that we have 2 images. One image that we draw on, and the other that we show on the screen. This way, we're always showing an image that is fully drawn and never an image that is incomplete.
E.g we have img1 and img2. We draw on img1 and once it has been fully drawn we save it in img2 and then we show img2 on the screen. Then we draw on img1 again, img1 hasn't been fully drawn yet, so we keep showing img2 on the screen, once img1 has been fully drawn, we save it in img2 and show it on the screen etc.