The resonant mode spectrum of the Kerr-Newman spacetime is presently unknown. These modes, called the quasinormal modes, play a central role in determining the stability of Kerr-Newman black holes and their response to perturbations. We present a new formalism, generalized from time-independent perturbation theory in quantum mechanics, for calculating the quasinormal mode frequencies of weakly charged Kerr-Newman spacetimes of arbitrary spin. Our method makes use of an original technique for applying perturbation theory to zeroth-order solutions that are not square- integrable, and it can be applied to other problems in theoretical physics. The new formalism reveals no unstable modes, which together with previous results in the slow-rotation limit strongly indicates the modal stability of the Kerr-Newman spacetime. Our techniques and results are of interest in the areas of holographic duality, foundational problems in General Relativity, and possibly in astrophysical systems.