We determine the average metallicities of the elements of cold halo substructure (ECHOS) that we previously identified in the inner halo of the Milky Way within 17.5 kpc of the Sun. As a population, we find that stars kinematically associated with ECHOS are chemically distinct from the background kinematically smooth inner halo stellar population along the same Sloan Extension for Galactic Understanding and Exploration (SEGUE) line of sight. ECHOS are systematically more iron-rich, but less α-enhanced than the kinematically smooth component of the inner halo. ECHOS are also chemically distinct from other Milky Way components: more iron-poor than typical thick-disk stars and both more iron-poor and α-enhanced than typical thin-disk stars. In addition, the radial velocity dispersion distribution of ECHOS extends beyond σ ~ 20 km s-1. Globular clusters are unlikely ECHOS progenitors, as ECHOS have large velocity dispersions and are found in a region of the Galaxy in which iron-rich globular clusters are very rare. Likewise, the chemical composition of stars in ECHOS does not match predictions for stars formed in the Milky Way and subsequently scattered into the inner halo. Dwarf spheroidal (dSph) galaxies are possible ECHOS progenitors, and if ECHOS are formed through the tidal disruption of one or more dSph galaxies, the typical ECHOS [Fe/H] ~ - 1.0 and radial velocity dispersion σ ~ 20 km s-1 implies a dSph with M tot >~ 109 M sun. Our observations confirm the predictions of theoretical models of Milky Way halo formation that suggest that prominent substructures are likely to be metal-rich, and our result implies that the most likely metallicity for a recently accreted star currently in the inner halo is [Fe/H] ~ - 1.0.