New upper bounds for robust stability are developed for block-structured real and complex uncertainty involving arbitrary spatial norms. Specifically, norm-bounded, block-structured uncertainty is considered wherein the defining norm is not necessarily the maximum singular value. In the case where the defining norm on the uncertainty characterization is set equal to the spectral norm, the resulting upper bounds generalize upper bounds for mixed-mu by permitting the treatment of nondiagonal real uncertain blocks as well as accounting for internal matrix structure in the uncertainty. The overall framework provides for a considerably simplified proof of the standard mixed-mu bound.