On écrit : « ils se sont téléphoné ». En règle générale, on accorde le participe passé lorsqu’il est associé à l’auxiliaire « être ». Mais dans le cas de l’accord du participe passé des verbes pronominaux, il peut arriver qu’il n’y ait pas accord. De là la confusion. Dans le cas de « ils se sont téléphoné », il n’y a pas accord car le pronom réfléchi de la troisième personne « se » a le rôle d’un complément d’objet indirect (COI). Pour rappel, un COI permet de répondre aux questions « à qui ? » ou « à quoi ? » s’applique un verbe. Pour savoir si « se » correspond à un COI, il suffit de changer l’auxiliaire « être » par l’auxiliaire « avoir » : 

Ils [se] sont téléphoné = ils ont téléphoné [à eux-mêmes]. 
Ils ont téléphoné à qui ? À eux-mêmes. 
Eux-mêmes, qui remplace « se », est un COI. « Se » est donc COI. 
Le participe passé « téléphoné » ne s’accorde pas. 

À lire ici : pourquoi dit-on « allô » au téléphone ?

Le cas est le même pour « ils se sont parlé » : 

Ils [se] sont parlé = ils ont parlé [à eux-mêmes]. 
Ils ont parlé à qui ? À eux-mêmes. 
« Se » est donc COI.
Le participe passé « parlé » ne s’accorde pas.

En revanche, on écrit bien « ils se sont appelés » : 

Ils [se] sont appelés = ils ont appelés [eux-mêmes]
Ils ont appelé qui ? Eux-mêmes. 
Eux-mêmes, qui remplace « si », n’est pas un COI, mais un COD (complément d’objet direct).
Or, selon la célèbre règle, lorsque le COD précède le participe passé, il y a accord. 

À lire ici : comment accorder « je soussigné » ?

Exemples avec « ils se sont téléphoné »

  • Malgré leurs emplois du temps chargés, ils se sont téléphoné hier soir pour se raconter leurs journées.
  • « Ils se sont téléphoné à nouveau ? — Vers cinq heures. Lina Nahour a simplement annoncé l’heure de son départ, en ajoutant que son amie l’accompagnerait. » (Simenon, Maigret et l’affaire Nahour)
  • « Elle est arrivée là-bas avant-hier.Ils se sont téléphoné deux fois, elle l’a bombardée de photos, de petits films, mais un peu moins que d’habitude. » (Adrien Goetz, La Constellation de Varengeville)