FIXED! I tried everything and was beginning to believe that the headphone jack was just broken. But, I'm thinking -- I hardly ever even USE it?!!? How??
So I rebooted, and tried all the above solutions and nothing.
Just for the !&&* of it, I just added a bluetooth speaker (DJKnight Magicbox II) -- As soon as the device was paired -- BAM the headphones showed up.
This just happened after an OS update, so it's NOT hardware or a worn out jack. This is definitely a bug. Adding a bluetooth speaker is just a work-around -- but it works and it's free.
Hope that helps.
Good luck!