Não liga mais para números da agenda

Possuo um Galaxy S4 com Android 4.4.2.

Há anos sincronizo a agenda de contatos com o Microsoft Outlook. Os números de telefone estão no formato (99) 9999-9999 (o DDD entre parênteses e hífen separando os 4 últimos dígitos).

Há alguns meses não consigo fazer mais ligações diretamente da agenda.

Quando tento, o número discado vem no formato 9999999999 (o DDD junto com o número, sem parênteses nem hífen), recebo a informação que o número não existe e a ligação não é realizada.

Para conseguir ligar, ou disco diretamente o número ou preciso colar na tela de discagem e editar o número antes de ligar, colocando 0 na frente, ficando 09999999999.

Ex.: O número 71 3247-2345 está armazenado na agenda como (71) 3247-2345. Mas só liga se for digitado como 0713247-2345 ou 3247-2345.

Sempre funcionou, mas após alguma atualização ou do Android ou da Samsung, não funcionou mais. Possuo uma agenda extensa e editar todos os números é inviável.

Alguém pode me dizer qual a atualização que fez essa mudança e/ou me ajudar a restaurar à situação anterior?