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 similar to 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] similar to -0.7) stars at v(hel) = -349.5 km s(-1), sigma(v,corr) similar to 5.1 +/- 2.5 km s(-1) 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] similar to-1.3) stars confined to a narrow, 15 km s(-1) velocity bin centred at v(hel) = -285.6, sigma(v,corr) = 4.3(-1.4)(+1.7) km s(-1) 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] similar to-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 similar to -400 km s(-1)). Spectroscopy near the edge of Stream 'B' suggests a likely kinematic detection at v(hel) similar to -330, sigma(v,corr) similar to 6.9 km s(-1), while a candidate kinematic detection of Stream 'A' is found (plausibly associated to M33 rather than M31) with v(hel) similar to -170, sigma(v,corr) = 12.5 km s(-1). 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.