I had the same problem. Following these instructions got my headphones working.
Open the terminal and enter the following commands:
cd /usr/share/pulseaudio/alsa-mixer/paths/
sudo cp analog-output-headphones.conf analog-output-headphones.bak
sudo nano analog-output-headphones.conf
Look for the section called [Element Speaker] and change it so that it looks like this:
[Element Speaker]
switch = on
volume = ignore
Save the changes and exit nano.
Create a backup of the corrected analog-output-headphones.conf:
sudo cp analog-output-headphones.conf analog-output-headphones.fixed
Now you can restore the fix if a future installation or update overwrites it.
Reboot.
After rebooting, you may need to remove and reinsert the headphone plug to get it to work. After it's working, though, you will be able to remove and insert the plug, and behavior will be as expected.
$ lspci | grep Audio
. This will show your audio chipset, among other things, e.g.00:1b.0 Audio device: Intel Corporation 7 Series/C210 Series Chipset Family High Definition Audio Controller (rev 04)