Emulsions and foams that remain stable under varying environmental conditions are central in the food, personal care, and other formulated products industries. Foams stabilized by solid particles can provide longer-term stability than surfactant-stabilized foams. This stability is partly ascribed to the observation that solid particles can arrest bubble dissolution, which is driven by the Laplace pressure across the curved gas-liquid interface. We studied experimentally the effect of changes in temperature on the lifetime of particle-coated air microbubbles in water. We found that a decrease in temperature destabilizes particle-coated microbubbles beyond dissolution arrest. A quasi-steady model describing the effect of the change in temperature on mass transfer suggests that the dominant mechanism of destabilization is the increased solubility of the gas in the liquid, leading to a condition of undersaturation. Experiments at constant temperature confirmed that undersaturation alone can drive destabilization of particle-coated bubbles, even for vanishing Laplace pressure. We also found that dissolution of a particle-coated bubble can lead either to buckling of the coating or to gradual expulsion of particles, depending on the particle-to-bubble size ratio, with potential implications for controlled release.