Graças ao viq no canal do IRC, consegui resolver este problema.
A solução é alterar a variável $ PATH do minion /etc/init.d/salt-minion
:
Altere isto:
PATH=/sbin:/usr/sbin:/bin:/usr/bin
por
PATH=/sbin:/usr/sbin:/bin:/usr/bin:/usr/local/bin
Você pode ter que chamar service salt-minion restart
no servo.