"Le informamos que el numero de destino no es valido; Por favor, revise el numero e intentelo de nuevo." [SOLUCIONADO] Versión rápida

Por si la versión larga de la solución de este problema te parece demasiado pesada, aquí tienes la versión simplificada, directa al grano.

Los pasos son los siguientes:

1. En Configuración -> Sincronización de datos

desactivar "Datos de fondo"

2. En Configuración -> Aplicaciones -> Administrar aplicaciones -> Contacts and MyFaves storage

clicar "Borar datos" (esto debe realizarse cada vez que reinicies el teléfono)

ATENCIÓN: Esto borra los contactos, deberás tenerlos guardados en la tarjeta SIM para recuperarlos.

3. Tendrás que recuperar los contactos de la SIM:

En Contactos -> Configuración -> Importar contactos -> Importar todo