What type of headset is this? It may need a firmware update:
http://www.plantronics.com/us/support/myheadset/updater/
Once you do that, you'll want to rebuild the bluetooth stack. Remove the device from your phone, power off, power back on, re-pair the bluetooth. That will rebuild the bluetooth stack and is best practice after updating firmware. (I spend A LOT of time on PLT's forums).
Also, I don't recommend the M series. They are the stupid cousin of the Voyager series.