Você está certo de que a caixa do Asterisk precisa transcodificar o áudio. Eu diria que tente configurar o Asterisk e seus telefones para usar o GSM e ver como funciona.
Eu estou supondo que o codec G729 é o que está causando a gagueira. Isso requer mais poder de processamento que muitos telefones não suportam, especialmente se você estiver fazendo chamadas de três vias.