Threading sprites (game objects) is a very bad idea. Having a thread for each sprite will cause many problems with for example collision detection (in your case punches). I don't know if this is what you are doing though, you were a little unclear...
Callbacks from keyboard events in Java2D/Swing (the KeyListener functions) are called from another thread, namely the AWT event thread. You should probably not do much more than save the key press here. Do not do health checks here (EDIT: I mean checking if your enemy/punchbag dies). Don't even do the collision testing of your punch here. I recommend keeping a boolean variable for the key state of each key you need (boolean isPunchLeftDown, isPunchRightDown; for example). The only thing you do in keyPressed() and keyReleased() is modify these variables if the correct button is pressed. Then check these variables in your game loop. I'll post some code if you don't understand.
Concerning flickering, I believe you are rendering directly to your JFrame/Frame/Applet or whatever you're using. The flickering occurs because your computer screen might update it's content while you are halfway through drawing. The solution is double buffering. Basically create a BufferedImage and render your game's graphics to it. When you are done copy the image (your back buffer) to your Frame/JFrame/Applet/whatever. Again, I'll post code if you want me to.
As you say your game randomly does not work, I believe you are experiencing a phenomena known as "deadlocking". It is when two or more threads are waiting for each other and they therefore freeze. This usually happens accidentally due to one thread modifying something another thread uses during a time when the variable is not expected to be modified. I don't know how much programming experience you have, but multithreading is fairly advanced. Synchronizing threads so they do not randomly freeze or crash is pretty hard and VERY hard to debug as the program can run fine until it seems to freeze without any clear reason. I recommend avoid multithreading as much as possible, but as you're using Java2D, you will have to split up your rendering and your game loop. The easiest way to avoid problems and synchronization is to keep clear rules of which variables a thread can modify. For a game loop thread and Java2D thread, it is pretty easy. The rendering thread shouldn't modify anything from the current game state as it should only read the position, color and/or images of your objects to be able to draw them.
It would be better if we kept the discussion public, as other people can read our posts and hopefully learn from them.
