549です。

パレットエントリを予め区画化しておいてから、最短距離を求める564氏の領域分割の提案を試しました。
テスト使ったのは、
・画像１ ＝ 色の種類は少ないが微妙なグラデーションが多い人物写真 336ｘ560、 51952色
・画像２ ＝ 色の種類は多いがグラデーションが少なめの街並み写真 512ｘ384、104730色

２５６色への量子化によるパレットエントリの決定
Gervautz-Purgathofer Octree Color Quantization Algorithm（http://www.microsoft.com/msj/archive/S3F1.aspx）

単純な巡回によるエントリ番号の決定では量子化過程も含めて 画像１ で 3723ミリ秒、画像２で 3870ミリ秒
かかります（私のPCでの３回の平均）。

今回は区画を区切ってオリジナルピクセル値が属する区画にエントリが存在するときはその中の最短値を、無い場合は
２５６回巡回するという単純な論理です。

RGBそれぞれ上位４ビットを使って４０９６区画の場合は、画像１は890ミリ秒、画像２は1437ミリ秒と３，４倍の効率化
上位３ビットの５１２区画の場合は、画像１は274ミリ秒、画像２は287ミリ秒と実に１３倍の効率化
上位２ビットの６４区画では、画像1が665ミリ秒、画像２が587ミリ秒と６倍くらいの速さです。

画質は、４０９６区画の場合は単純巡回の場合とほとんど同じですが、画像１では微妙なグラデーションに差があります。
５１２区画ではグラデーションの差が拡大しますが画像２では見分けがつきません。
６４区画では、さらに単純法よりグラデーションの結果が異なりますが、やはり画像２では見分けがつきません。

この方法の成否は、オリジナル画像からのパレットエントリを決定する量子化過程が重要です。その意味でも上記の量子化
は満足すべき結果を与えてくれました。なにより、今回の質問の処理よりものすごく高速です。

以上より、RGBおのおの上位３ビットを採用する512区画にすることにしました。最終的には誤差分散をしているので
得られる画像は単純法と見分けがつきませんし、１０倍以上の速さは体感速度としても十分で大満足です。

みなさん、ありがとうございました。