Разобрался сам:

1. При paste() из индексированного в индексированный различия палитр не учитываются. Синий стал жёлтым из-за того, что серия оттенков жёлтого в 1-ой палитре и синего во 2-ой имели одинаковые индексы.
2. При paste() из RGB в индексированный для вставляемого вызывается convert(), который в свою очередь вызывает quantize() с какой-то своей палитрой. Отсюда красные пятна на месте некоторых оттенков синего.
3. Чтобы преобразовать индексированную картинку к другой палитре, нужно сперва вызвать convert( mode='RGB' ), затем quantize() с требуемой палитрой.
4. Если нет подходящих цветов, quantize() добавит регулярную сетку пикселей для получения в среднем нужного цвета. Полезно на больших разрешениях, вредно на малых — в моём случае.
5. Чтобы этого избежать, можно заменить цвета во 2-ой палитре близкими цветами из 1-ой.
6. Правильный вариант скрипта: https://www.linux.org.ru/forum/development/14517401?cid=1451... Буду рад советам, как его ускорить.