Hoje os Correios fizeram uma mudança no código dos serviços SEDEX e PAC, e com isso o plugin WooCommerce Correios, que usa a API oficial, não retorna mais os valores corretos até haver uma atualização. Além disso, os Correios ainda não divulgaram a mudança nos canais oficiais, aparentemente.
UPDATE: na verdade faltou atenção :) Uma solução ainda mais simples é ir WooCommerce -> Configurações -> Entrega -> editar cada área de entrega e mudar PAC e SEDEX para os novos valores:
- PAC: 04510
- SEDEX: 04014
- PAC com contrato: 04669
- SEDEX com contrato: 04162
=========
Para resolver o problema, fiz esse pequeno código para ser adicionado ao functions.php do seu tema. Após o plugin WooCommerce Correios ser atualizado, não esqueça de removê-lo.