Por fin lo solucioné, llegué a restablecer el móvil de fábrica y seguía con el problema.
Resulta que al final era configurar el APN de la red móvil, estoy con Pepephone. Era algo que había descartado porque si tenía acceso a internet ya que otras apps no me fallaban.
Un saludo.