hundreds of images on a rendering scene

I have a problem when displaying 400 images in each frame (i have got map with 20x20 tiles - small png files of size - 32x32). Earlier when i was rendering in every frame only those tiles which changed from earlier frame (like an vehicle was passing the frame,etc) evertyhing was OK - animation was smooth. Unfortunatelly i could not use then double buffering and moreover requirements changed and now i must add scrolling of a map which i think makes the idea of partial rendering useless.
So now i repaint the whole scene in each frame but i found that animation is not smooth at all now! Moreover the CPU is utilized in 100%!! Game uses now 100% of the CPU when it is running in e.g. 40 FPS as well as if it is ran with 100 FPS. I commented delays in a game loop and measured the FPS and its about 1000FPS!! So why is it than that if i set it to run with 40FPS its using 100% CPU? And what is more imoportant why the animation is not smooth now (its not smooth with 40FPS, 100FPS, 1000FPS - it does not matter only vehicles moves faster, but not smooth). I use BufferImages and draw them with Graphics2D interface.

Thanks in advance for the help
regards