I tried replicating this problem, but the substitution works fine for me. Here's the code I used:
Symbol xs = ctx.mkSymbol("xs");
EnumSort xSort = ctx.mkEnumSort(xs, ctx.mkSymbol("A"),ctx.mkSymbol("B"));
SetSort xSet = ctx.mkSetSort(xSort);
Expr x = ctx.mkConst("x",xSet);
Expr z = ctx.mkConst("z",xSet);
Expr f_old = ctx.mkEq(x, z);
System.out.println("old: " + f_old);
Expr y = ctx.mkConst("y",x.getSort());
BoolExpr f_new = (BoolExpr)f_old.substitute(x, y);
System.out.println("new: " + f_new);
And this code prints, exactly as expected:
old: (= x z)
new: (= y z)
Is this not the case for you?