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 CFHT/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 \sim 70 % 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 ] \sim -0.7 ) stars at v _ { hel } = -349.5  km/s , \sigma _ { v,corr } \sim 5.1 \pm 2.5 km/s are proposed as a serendipitous detection of Stream ‘ Cr ’ , with followup kinematic identification at a further point along the stream . Six metal-poor ( [ Fe/H ] \sim -1.3 ) stars confined to a narrow , 15 km/s velocity bin centered at v _ { hel } = -285.6  km/s , \sigma _ { v,corr } = 4.3 ^ { +1.7 } _ { -1.4 }  km/s represent a kinematic detection of Stream ‘ Cp ’ , again with followup kinematic identification further along the stream . For the cluster EC4 , candidate member stars with average [ Fe/H ] \sim -1.4 ( [ Fe/H ] _ { spec } =-1.6 ) , are found at v _ { hel } = -285  km/s 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 \sim - 400 km/s ) . Spectroscopy near the edge of Stream ‘ B ’  suggests a likely kinematic detection at v _ { hel } \sim - 330  km/s , \sigma _ { v,corr } \sim 6.9 km/s , while a candidate kinematic detection of Stream ‘ A ’  is found ( plausibly associated to M33 rather than M31 ) with v _ { hel } \sim - 170  km/s , \sigma _ { v,corr } = 12.5 km/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 .