While this patch indeed fixes bug 2666, it also kills performance, at least with Age of Empires II. The frame rate in the menu for me is about one frame every three seconds and about 1 fps in-game.
With the patch, the work previously done by X11DRV_DIB_MapColor is now done by X11DRV_DIB_GetNearestIndex. Unlike GetNearestIndex, MapColor avoids traversing the entire palette most of the time by reusing the previous index in the destination bitmap if the color has not changed. However, MapColor only checks for exact matches and returns the first palette entry if none was found, effectively causing bug 2666. A possible solution is to have MapColor call GetNearestIndex as a last resort instead. This both fixes the problem and results in acceptable performance.
David