Hola!
Hace y mucho tiempo, cuando compre el móvil me pasaba lo mismo mismo y explique alguna veces mi solución.
Me di cuenta que solo me pasaba con algunos contactos, que precisamente eran los que contactos que había importado de Gmail y que tenían foto (era mi familia) borrando esos contactos y generandolos de nuevo se soluciono.
Podéis hacer la prueba con un contacto, de estos que os digan que no se puede contactar con vosotros... Lo borrais y lo hacéis de nuevo. Si funciona y tenéis la solución.
Espero que os sirva!
Un saludo