Try deleting all stored devices in the bluetooth menu. I could not pair my phone in my 6 either until I tried deleting all paired phones then retrying a pairing to my phone. Instant success! Go to "setup">"pairing options">"delete phone" and chose "delete all". This might not work but worth a try anyway. Have you thought of taking it back to the seller and asking him to sort it,or as a last resort take it to a Mazda agent. Having checked my Mazda manual I can see no reference to resetting the bluetooth radio(despite having a comprehensive section on bluetooth), so apologies for not being more helpful.