Samsung Galaxy SIII mám taky a zažíval jsem podobný problém. Respektive příběh má vývoj: Když jsem mobil koupil, spároval se na první brnk a bez problémů jsem telefonoval asi 3 - 4 měsíce. Pak přišla první (pro mě) aktualizace firmware (to bylo někdy cca v srpnu 2012). A s tím začaly problémy - telefon se sice s rádiem našel, ale po několika desítkách sekund až minut se odpojil a po nějaké době zase připojil. Když se telefonovalo, tak to drželo, ale když bylo BT spojení jen udržovací, tak to furt dingalo. Pomohla až další aktualizace FW, která se ovšem zase vyznačovala tím, že když se telefon odpojil (resp. se mezi tím připojil jiný telefon), tak už se můj telefon odmítal připojit a pomohlo jenom "výrobní nastavení" rádia. Po poslední (nedávné aktualizaci na 4.1.2) to, jak se zatím zdá, dělá opět dobrotu a funguje to tak, jak má (akorát mi blbne wifi, která i na známé sítě čas od času hlásí "chyba ověření", ale to už je jiná pohádka).