Which new car? Mazda (part number would seem to indicate that). I believe, but can't be sure, that this is what we call a Nav2 device. Should be a 2GB "Live" device, yes.
"...it says my phone..." What is "it"? The in-dash nav system, or a list somewhere on the TomTom site? If the latter, do you have a link?
It's quite unusual that not even voice connections work (phonebooks, SMS and the like are another story). The usual A2DP audio profile is pretty universal for phones, too.
Did you attempt to pair the two devices? At what point did the pairing fail, and what messages were received on each side?