Had this problem today with my galaxy 5. Pulled battery, insterted headphones and aux cable that started the problem, tried to clean out the jack input..felt like it was a lost cause, as none of these above methods worked. I downloaded the soundabout app, which gave me a temporary fix(because you can use a speaker option to still hear and use voice without the headphones,whether in or not )..I ended playing the same downloaded music track in my "play music" that I had listened to last night before this problem started..and magically, once the tunes were over.boom.headphone issue went away...I turned off the soundabout app, and everything seems to be in working order..