We study spin-dependent shuttle phenomena in a nanoelectromechanical single electron transistor (NEM-SET) with magnetic leads by considering the coupling between the transport of spin-polarized electrons and mechanical oscillations of the nanometer quantum dot. It is shown that there are two different bias-voltage thresholds for the shuttle instability in electronic transport through the NEM-SET, respectively, corresponding to parallel (P) and antiparallel (AP) magnetization alignments. In between the two thresholds, the electronic transport is in the shuttling regime for the P alignment but in the tunneling regime for the AP one, resulting in a very large spin valve effect.