Seguramente no tienes bien asignadas las zonas. La verdad es que el tema de las zonas funcionan bien, pero la configuración que tienen es un poco confusa y mucha gente se vuelve loca hasta que averigua cómo funcionan (a mí me pasó en su momento).
Te resumo cómo debería estar configurado
1.- Internacional -> Ubicaciones geográficas -> Zonas. Ahí deberías crear una zona para cada zona de reparto que usen los transportistas. Por ejemplo, una zona puede ser "España - península", otra "Islas Baleares", otra "Islas Canarias" y otra "Ceuta y Melilla" (los nombres puedes poner los que quieras):
2. Internacional -> Ubicaciones geográficas -> Provincias. Debes asignar cada provincia a su zona correspondiente. La asignación masiva NO funciona (al menos a mí no me ha funcionado nunca), así que hay que ir modificando provincia por provincia y asignándola a una de las zonas anteriores:
3. Transporte -> Transportistas. Dentro de cada transportista, en la pestaña "Localización de destino y gastos de envío", debes marcar las zonas a las que sirve ese transportista y dejar desmarcado el resto, establecer el precio a cobrar para cada zona, y si va por tramos de precio o peso de productos, añadir los rangos que sean necesarios. Por ejemplo, te pongo un transportista que solo sirve a península y Baleares, y tiene envío gratis por encima de 50 euros para la península:
Deberás configurar así todos los transportistas, por ejemplo otro que solo sirve a Canarias y sin rangos de precio para envío gratis:
Una vez configurado todo así debería funcionar correctamente: En cuanto el comprador introduce su dirección le aparecerían solo los transportistas que sirven en su zona y luego, dependiendo de cómo lo hayas configurado en transporte -> preferencias, aparecerían ordenados por precio, posición, o como lo establezcas tú:
Añado: Si quieres que a los "invitados" (a los que no han iniciado sesión) les aparezca un precio de envío determinado, puedes usar un truco: En la pestaña "Tamaño, peso y grupo de acceso" de cada transportista especificar que sean solo para los grupos "Cliente" (y si tienes creados más grupos, para los que sean, excepto "Visitante" e "Invitado"). Y luego crear un transportista especial, que se aplique solo a esos dos grupos ("Visitante" e "Invitado"), y darle a ése el precio que quieras que muestre a los invitados. De ese modo a los invitados solo les aparecerá ese precio, y en el momento que inicien sesión ya les aparecerá el correspondiente a su zona.