I just started having the exact same issue today - I just wanted to let everyone know that there's another one out there.
I too have the latest update and, like K8lyn, I also had Car Mode pop up really frequently without notice. Every now and then the headphones will work for a bit and then...