In this paper we introduce new lower and upper robust stability bounds for structured uncertainty involving arbitrary spatial norms. Specifically, we consider a norm-bounded block-structured uncertainty characterization wherein the defining spatial norm is not necessarily the maximum singular value. This new uncertainty characterization leads to the notion of structured matrix norms for characterizing the allowable size of the nominal transfer function for robust stability. The lower and upper bounds are specialized to specific matrix norms including Holder, unitarily invariant, and induced norms to provide conditions for robust stability with several different characterizations of plant uncertainty. One of the key advantages of the proposed approach over the structured singular value is the reduction is computational complexity gained by directly addressing a given uncertainty characterization without having to transform it to a spectral-norm type characterization. Finally, we introduce a performance block within the structured matrix norm framework to address robust performance in the face of structured uncertainty.