Mate,
I'm new to this forum (only joined a few minutes ago) so apologies if you've sorted this out.
I had trouble with my last phone (Nokia E63) and it's bluetooth compatibility with my car radio. Ended up the only way I could get around it was to replace the car radio.
In my investigations through both the Nokia and Parrot (worlds major bluetooth manufacturer) websites I found out that bluetooth ain't just bluetooth.
Not all bluetooth appliances will mate and not one manufacturer seems to care. There are different standards and sometimes things won't partner up.
Good luck in your search.
An edit in minutes; Forgot to mention in the search for a new car radio I went to many hi-fi and auto shops and tried scores of differnet brands of radios. Strangely the kenwood radio I ended up with had refused to work at another branch of the same auto shop chain.