I just brought home my used 2009 GT w/ navi this week. I wanted to setup the bluetooth connection to my blackberry. I discovered that the previous owner had enabled a passcode for the bluetooth. I couldn't access any of the bluetooth setup features without this code. I couldn't find anything in the manual about resetting the bluetooth passcode so I called Mazda handsfree support. I'll share the process of removing the code:
1) Turn on car and set sound source to AM/FM radio.
2) Push in the volume (power) and tune (audio) knobs at the same time
3) You should now see a "failure analysis" screen on the nav
4) Type in the two-digit code "39" and hit enter
5) The nav will ask you if you want to reset the code. Hit enter to confirm.
6) Finally push the volume (power) knob to return to the map.
The bluetooth code is now removed. The phone device settings and phone book are still intact. I hope this saves someone else a couple hours of head scratching.
This also works on the Mazda CX7 with touch screen navigation display.