I have a Sony car stereo that was designed to interface with the iPhone. When I upgraded to OS4, it stopped working.
After a little research on the Apple forums, I decided to try a hard reboot (home and on/off buttons) while connected to the stereo.
After the hard reboot (and restart) it works fine again.
It may not work with all brands, but people are having varying levels of success with this.