Me respondo a mí mismo, por si a alguien le hace falta...
Ya sé el motivo y la solución. El tema fue que metí los contactos por medio de un backup antiguo que tenía. Imagino que la transferencia no fue del todo correcta ya que, aunque tenía los contactos y podía llamarles, la Base de Datos del móvil no los pillaba bien.
Para solucionarlo sólo hay que entrar uno por uno de los contactos y darle a editar. Entras en el número del contacto y, sin tocar nada, le das a OK y sales de la pantallita del contacto.
Con esto, el teléfono incorpora el número a su BD y lo coge bien.
La razón científica no la conozco... pero me funciona!! jeje
Un saludo y gracias por todo