If each tile can be changed asynchronously, then you probably want some sort of subtle animation on the selected tile. Users tend to assume that motion indicates that the system is working on something, even if that motion is only produced on the client and is unconnected with the backend that is doing the actual work.
If your users are typical web users, you can expect they’ll be familiar with the rotating symbol you suggest, especially if it mimics the IE throbber or buffering symbol in Flash videos. But users associate these with annoying delays, so maybe you want something more entertaining and consistent with your metaphor. Maybe the selected tile flips end over end, where, on the last flip, the front side has the new color.
Ideally, the animation would provide an indication of progress at the back end (e.g., show the old colored tile being slid out or chipped away in synch with actual progress), but that’s probably too much to ask for in a web app, and not necessary given your relatively short processing times.
Animation can be distracting, and, if user testing shows that’s a problem, then you need to go to some sort of static indication that input is received but not completely processed. You want some kind of tentative appearance, but the problem I see with changing to a neutral color is that users may think the app is changing the tile to the wrong color. Maybe it would be better to fade or dither the current color, especially if the user cannot command another change to the tile until after first change is processed (i.e. it’s essentially disabled). Perhaps the simplest and most effective static feedback would be the text “Changing…” superimposed over the tile.
If each tile change is synchronous, then your feedback needs to indicate the whole 16x16 matrix is disabled, distraction is less of an issue (there’s nothing to distract the user from), and it becomes even more important to have an entertaining and/or informative indication of process. Be creative and go wild.
Depending on your users and work environment, you may also want to consider supplementing the visual indication with an audio indication that the processing is occurring. This might be especially effective if you have no animation. The sound should be a quiet pleasant modulation that remains in the background, maybe like “bip-bip-bip-bip,” or something consistent with your metaphor. With only 256 tiles you could probably give each tile a unique sound (e.g., each is a different combination of frequencies determined by the row and column, like touch-tones in a phone). Or maybe the sound indicates the old color and/or known parameters for the new color, depending on how many colors you have. Just include a prominent control for users to mute the sound if they want.