In this paper, we study certain moduli spaces of vector bundles on the blowup of the projective plane in at least 10 very general points. Moduli spaces of sheaves on general type surfaces may be nonreduced, reducible and even disconnected. In contrast, moduli spaces of sheaves on minimal rational surfaces and certain del Pezzo surfaces are irreducible and smooth along the locus of stable bundles. We find examples of moduli spaces of vector bundles on more general blowups of the projective plane that are disconnected and have components of different dimensions. In fact, assuming the SHGH Conjecture, we can find moduli spaces with arbitrarily many components of arbitrarily large dimension.