The halo region of M31 exhibits a startling level of stellar inhomogeneities, the most prominent of which is the "giant southern stream". Our previous analysis indicates that this stream, as well as several other observed features, are products of the tidal disruption of a single satellite galaxy with stellar mass ~10^9 solar masses less than 1 Gyr ago. Here we show that the specific observed morphology of the stream and halo debris favors a cold, rotating, disk-like progenitor over a dynamically hot, non-rotating one. These observed characteristics include the asymmetric distribution of stars along the stream cross-section and its metal-rich core/metal-poor sheath structure. We find that a disk-like progenitor can also give rise to arc-like features on the minor axis at certain orbital phases that resemble the recently discovered minor-axis "streams", even reproducing the lower observed metallicity of these streams. Though interpreted by the discoverers as new, independent tidal streams, our analysis suggests that these minor-axis streams may alternatively arise from the progenitor of the giant southern stream. Overall, our study points the way to a more complete reconstruction of the stream progenitor and its merger with M31, based on the emerging picture that most of the major inhomogeneities observed in the M31 halo share a common origin with the giant stream.