We present a spectroscopic analysis of five stellar streams ("A", "B", "Cr", "Cp" and "D") as well as the extended star cluster, EC4, which lies within Stream "C", all discovered in the halo of M31 from our Canada-France-Hawaii Telescope/MegaCam survey. These spectroscopic results were initially serendipitous, making use of our existing observations from the DEep Imaging Multi-Object Spectrograph mounted on the Keck II telescope, and thereby emphasizing the ubiquity of tidal streams that account for ~70 per cent of the M31 halo stars in the targeted fields. Subsequent spectroscopy was then procured in Stream "C" and Stream "D" to trace the velocity gradient along the streams. Nine metal-rich ([Fe/H]~-0.7) stars at v_hel_=-349.5km/s, {sigma}_v,corr_~5.1+/-2.5km/s are proposed as a serendipitous detection of Stream "Cr", with follow-up kinematic identification at a further point along the stream. Seven metal-poor ([Fe/H]~-1.3) stars confined to a narrow, 15km/s velocity bin centred at v_hel_=-285.6, {sigma}_v,corr_=4.3^+1.7^_-1.4_km/s represent a kinematic detection of Stream "Cp", again with follow-up kinematic identification further along the stream. For the cluster EC4, candidate member stars with average [Fe/H]~-1.4, are found at v_hel_=-282 suggesting it could be related to Stream "Cp". No similarly obvious cold kinematic candidate is found for Stream "D", although candidates are proposed in both of two spectroscopic pointings along the stream (both at ~-400km/s). Spectroscopy near the edge of Stream "B" suggests a likely kinematic detection at v_hel_~-330, {sigma}_v,corr_~6.9km/s, while a candidate kinematic detection of Stream "A" is found (plausibly associated to M33 rather than M31) with v_hel_~-170, {sigma}_v,corr_=12.5km/s. The low dispersion of the streams in kinematics, physical thickness and metallicity makes it hard to reconcile with a scenario whereby these stream structures as an ensemble are related to the giant southern stream. We conclude that the M31 stellar halo is largely made up of multiple kinematically cold streams.