Pode ser que o seu sudo use PATH definido no arquivo /etc/sudoers , não o PATH da raiz. Verifique man 5 sudoers , procure a opção secure_path .
Você também pode ler o Como tornar sudo preserve $ PATH?
Dica: use visudo para editar /etc/sudoers . A ferramenta faz alguma verificação de integridade e pode salvar você da situação quando perder o acesso do sudo devido à edição inválida.