Good news... I tried it again last night, and it worked!
Could be because of any 3 possibilities:
1.) The night I originally tried, it was sub 20deg F outside and the car needed to be warmer for the BT to work
2.) I deleted all of the other phones from the Mazda Bluetooth
3.) I tried to reset the BT of my car following this random dude's weird instructions... "you need to hold down radio power button, 5 and seek down (all 3 together) for a minimum of 2 seconds, then AUTO M and 2 for a few seconds, should show cleared on the display then Bluetooth is reset back to factory for you." but I never saw any update on the screen.