[Alexej77]

Drongo, конечно, можно написать такую "штуку". На VBA вообще очень много чего можно, если скорость не сильно критична.
Думаю, так (на примере одной колонки):
1. Определить кол-во ячеек, подлежащих сортировке.
2. Создать массив с двумя столбами: содержимое ячейки и ее цвет.
3. Отсортировать этот массив по цвету.
4. Засунуть содержимое массива обратно в ячейки, начиная с первой, не забывая раскрасить в нужный цвет.

Или так:
Написать функцию, которая определяет цвет ячейки.

Код:

Function cellcolor(cell As Range) As Integer
    cellcolor = Range(cell.Address).Interior.ColorIndex
End Function

Эту функцию прописать рядом с теми ячейками, которые надо отсортировать. А потом сортируем по этим двум столбцам.