We report measurements of the quantum Hall state energy gap at avoided crossings between Landau levels originating from different conduction band valleys in AlAs quantum wells. These gaps exhibit an approximately linear dependence on magnetic field over a wide range of fields and filling factors. More remarkably, we observe an unexpected dependence of the gap size on the relative spin orientation of the crossing levels, with parallel-spin crossings exhibiting larger gaps than antiparallel-spin crossings.