I don't think it's evaluating the expression at all. Rather, I think it's taking the color of whatever the leftmost dimension value in your chart happens to be. That's why sorting or selecting can affect the color.
Another imperfect workaround is to create a simple second chart, remove everything but the legend from it, remove the legend from your original chart, and put the new chart on top of the old. See attached.
Or you can build a legend from four text boxes. I've resorted to that at least once before.