I had the same problem but after rebooting the device a few times fixed it.
From what I remember, this is what I did,

>Insert the headphone and then shutdown and restart. make sure headphone is working, stop the music.
>Then remove the headphone , restart.

I remember doing sth like this and it got okay after that.. I dont have that problem anymore.