Cierto, es algo muy extraño.
Se me ocurre que a la hora de definir el transportista por rangos de precio o peso no estén correctamente rellenos o incluso que los productos que hayas añadido no se contemplen en dichos rangos, por ejemplo por peso, si indicas rangos de 0-20kg y de 30-40kg cuando algun cliente añada productos de peso 25kg no estaría dentro del rango y te mostraría ese mensaje (si no indicas aplicar Fuera de la gama de comportamiento).
Si no es nada de esto, haz algunas pruebas más, como compruebr que el cliente registrado está correctamente asignado al pais o zona.
Otra prueba para descartar fallos de ese transportista en especial, reconfiguralo como transporte gratis, exactamente igual que tu transportista gratuito y comprueba si así te aparece. Si siguiera sin aparecer ese transportista es defectuoso o hay algun error de programación.
Prueba a crear otro transportista distinto, yo he tenido experiencias similares y lo he podido corregir añadiendo otro transportista.
Un saludo.