We show that combining the published Pierre Auger Observatory measurements of the longitudinal and lateral properties of UHE atmospheric showers, points to an unforeseen change in the nature of particle interactions at ultrahigh energy. A "toy model" of UHE proton-air interactions is presented which provides the first fully consistent description of air shower observations. It demonstrates that the observed energy dependence of the depth-of-shower-maximum distribution may not indicate a transition to a heavier composition, as commonly assumed. While fundamentally phenomenological, the model is based on considerations of how the normal vacuum of QCD might be vaporized and chiral symmetry restored by the extreme energy densities produced in UHE collisions. Whatever its origin, understanding this unexpected phenomenon opens exciting directions in particle physics and may impact Early Universe cosmology.