Galaxy S4 - Problema com Fone de Ouvido: Não conecta!!!

Bom pessoal, venho aqui pedir ajuda de vocês para solucionar meu caso. Recentemente eu atualizei meu Galaxy S4 para o Android 5.0.1, porém com 1 dia de uso o fone de ouvido não conecta mais, explico: com o celular zerado, o fone ainda funcionava, porém depois de um tempo usando ele, um dia mais ou menos, o fone não é mais reconhecido. O problema não é o fone, já testei mais de 6 e nenhum funciona, e em outro celular e até notebook funciona; o problema também não é sujeira, está limpo; e também não é o encaixe que está estragado, pois semana passada levei na Autorizada e eles relataram que não havia nenhum problema com a peça. Porém eu percebi que tem uma maneira do fone voltar a funcionar, que é zerando o celular, não apenas restaurando normal, tem que ir no wipe e limpar a data. Porém só funciona por algum tempo, apenas no início dele "novo", depois de um tempo para de funcionar de novo. Concluindo, não sei se esse caso já aconteceu com algum de vocês, creio que o problema seja o software, e queria saber se tem alguma maneira de arrumar isso, porque está complicado aqui.

Obrigado .