I have the same issue. My simple car AUX cable, when removed from the phone, disables my speaker unless I turn it into speaker phone. Fixing the actual problem involves rebooting my phone.
Flaw #2 I've found, is that the Droid does not work with the AUX cable and car charger attached. I'm NOT having the same problem as other people with the music stopping, I have major static and washed out sound issues when both are plugged in.
I will be taking my Droid back to VZW tomorrow to see if they will replace mine. My headphone issue is driving me crazy. I use my phone to listen to music on the way to work, and on the plane twice a week, and when I'm working out. EVERYTIME I unplug my headphones or aux jack I have no sound and have to reboot the Droid. I'm also getting some static in the sound quality. Hopefully I get one of the magic Droids where the jack actually works everytime...
Have you tried a different pair of headphones?