Yes, it crops up from time to time. In my case, I am not able to run a 4.0.4 version of CM9 or I lose BT Audio streaming to my Toyota. I currently run the 4.0.3 version from 3/18 and it works great.
Several others have posted various problems with an array of manufacturers, while a larger portion report that everything works great.
I have seen this same phenomenon since my previous phone (Captivate on CM7), and it seems to change over time with versions, ROMs, radios... nothing consistent I can point at and say THAT IS THE PROBLEM.
However, after just looking at your thread in the Sprint section, we are not talking about the same problem I suspect. I never have any trouble pairing the device, and in fact my stereo will show the connected icons fine. It just wont actually play audio, though the phone portion still works. That is what we usually see here (I think), and jives with my past experience too.
I suggest getting into the BT setup screen on your phone, and just before your stereo tells you to "use your phone to connect", hit the scan button so your phone is actively scanning when the stereo starts broadcasting. I have had the phone seemingly not scanning in time, and erroring out instead of asking for PIN, but doing the above seems to help.
Good luck.