O motivo é simples, cd é um shell embutido (e função shell em alguns shells), enquanto echo é tanto um binário quanto um shell embutido:
$ type -a cd
cd is a shell builtin
$ type -a echo
echo is a shell builtin
echo is /bin/echo
sudo não pode manipular builtins de shell, mas pode manipular binários no $PATH . Quando você usa sudo echo , /bin/echo é encontrado no $PATH , então ele usa isso, enquanto sudo cd não consegue encontrar cd no $PATH , portanto, ele falha.