I use a palette of separate images and each map cell points one of them. My MapDisplayExample is using a map with 2500 cells (displaying about 300 of them at a time) and it is very fast.
I am working on a new game where each map (level in this case) contains 28,620 cells and haven't seen a speed problem. Now understand I'm working on a 1.2Ghz system.
I would like to know what your 333Mhz does with the MapDisplayExample. Please give it a try and let me know how it performs.http://www.java-gaming.org/cgi-bin/JGOForums/YaBB.cgi?board=share;action=display;num=1036252001;start=15
Check this thread, the first message describes how to run the example and the last a link to the latest code.
Edit: Looking at your post again I'm wondering why if you have a map of 400 tile cells you use 400 different images? Is every cell different in appearance? If not then loading a single image for the map would seem to be more efficient. Perhaps this is because of the random requirement you have. In that case I would still create a single map image (as a VolatileImage from the cell images) and blit that to the screen. That should be a lot faster than making 400 drawImage calls.