I think what's happening is that the Mean of the rows represented by the cells is the Mean of Type's ordering index. With the new order, the Mean for that heatmap cell's Type is now between 0(edge) and 1(void), so both patterns are displayed, whereas before the Mean of Types 0(edge) and 2(void), was 1 (other).
Before the reordering, when clicking on the other group, only cells representing rows with "other" as their Type were selected not cells with the Mean of the Types being "other".
When clicking on the cell that contained rows with "void" and "edge", only those two Types were highlighted in the legend.