I found i got slightly better images if I treaded the RGB values as a vector in 3d(R3 space) and used distance formula to find the 1 dimensional distance between the two vectors. The difference was small but noticable.

IE: distance = sqrt( (Roriginal-Ricon)^2 + (Goriginal-Gicon)^2 + (Boriginal-Bicon)^2 )

The other thing I did a bit different from you was rather than go on a pixel by pixel basis to analyze my original image, I used a larger block of pixel. Instead of averaging the entire icon as a single RGB value, I analized it as a 4x4 grid of RGB values, in effect, simplifying it to a 4x4 pixel image. I then compared those 4x4 values to a 4x4 block of values to my image being mosaic'd and used the same vector formula, but in a 48-dimensional way to find the closest match.

Here's the icon pack. I've hosted it myself cause I can't find the original. http://video.cliffmonkeys.com/WoW_wExp1-2_Icons.zip