We present the first results from our survey of stellar substructure in the outskirts of M31 using the Advanced Camera for Surveys (ACS) on board the Hubble Space Telescope. We discuss the stellar populations associated with five prominent stellar overdensities discovered during the course of our panoramic ground-based imaging survey with the Isaac Newton Telescope Wide-Field Camera (INT WFC); a sixth pointing targets a region of `clean' halo. The colour-magnitude diagrams (CMDs), which contain between ~10,000--90,000 stars and reach four magnitudes below the horizontal branch, reveal clear variations in morphology between most fields, indicating that the age and/or metallicity mix of stars is not constant at large radius. This directly confirms the existence of large-scale population inhomogeneities within the halo of M31 and lends further support to the notion that M31 has formed, at least in part, through satellite accretions. We find a striking similarity between the populations of the giant stellar stream and those of another overdensity, the NE shelf, which lies north-east of the galaxy center. If these overdensities are associated with the same population, then the difference in their red clump magnitudes implies the NE shelf lies in front of the stream by several tens of kpc, in good agreement with recent orbit calculations for the stream progenitor.

5 pages, 3 figurs, ApJL accepted