Você não deve ter um /usr/local/bin/sudo
, isso é o que está quebrando as coisas (não a alteração da senha). Mova-o para fora do caminho:
/usr/bin/sudo mv /usr/local/bin/sudo{,2}
e depois diga ao seu shell sobre isso:
hash -r
Isso restaurará a funcionalidade sudo
com a qual você está acostumado.