Yo hace poco me cambié a Yoigo, y tuve algo parecido a tu problema. El móvil automáticamente me configuró la apn correspondiente (en este momento tenía 4G), pero Yoigo luego me envió un mensaje con su configuración de apn, y le di aceptar (se acabó el 4G en el móvil). Con esto me quiero referir, a que igual necesitas otra configuración de apn para que se active el 4G. Yo llamaría a Movistar y les comentaría el problema. Si no te lo solucionan, prueba a buscar por San Google, seguro que ha alguien le ha pasado algo parecido con otro dispositivo.
Un saludo
Enviado desde mi MotoG3 mediante Tapatalk