The island of Tsushima is written 対馬{つしま}. Why? No reading of 対 and 馬 can produce つしま, and clearly つしま has something to do with 島{しま}. There seems to also be no gikun-type motivation in meaning to write 対馬, which honestly is a weird name for an island ("against a horse"?).
The Korean and Chinese names do use the characters 対馬 and Chinese-based readings though (daema and duima). However, it seems unlikely that the Chinese/Korean name came first, as the island is Japanese throughout history. In any case, even if 対馬 came from Chinese, why keep the つしま name?
considering how many sound changes take place in Japanese
Not very many irregular changes. – ithisa Dec 2 '13 at 11:39