That part is being reworked (see this github comment and the discussion there in general).
There is a conceptual issue with the current approach where the keys of the dictionary in pal do not match the transformed entries for your categorical variable (which are no longer just strings but strings + sorting information).
A “hack” around it would be to pass the transformed values to the palette, e.g.
labels = ["x", "z", "y"]
d = (x='a':'c', y=[1, 2, 3], c=labels)
transf = sorter(d.c)
pal = [transf("x") => "red", transf("y") => "blue", transf("z") => "green"]
p = data(d) * mapping(:x, :y, color=:c => transf) * visual(BarPlot)
draw(p, palettes = (; color=pal))
But the long term fix is probably to decouple the palette (which really should just be a list of color) and the “categorization of the variable” (convert from strings or other types to integres) in AlgebraOfGraphics.jl
EDIT: but yes, definitely do file an issue about this, it’s a valid use case to keep in mind when reworking the palette system