Check that you have a pair of convex/concave washers on both sides of the brake arm. Otherwise, the shoe will be forced to whatever orientation the flat side dictates. Note that on some shoes, one of the convex shapes is integral to the holder, and only the matching washer goes between the holder and arm. Then the other pair goes between the arm and nut.

If you have two pairs, make sure they're oriented right, with mating curvatures to each other and flat side out.

Now if all else is right, two possibilities come to mind. The first is that the arms are twisted relative to the rim beyond the adjustment range the washers provide. The other, and more likely one, is that you're not holding the shoe steady and allowing it to move as you tighten.