Eu acho que o ato de trazer a interface faz com que ele releia o mac do hardware. O método recomendado de usar 'macchanger' é escrito no link , e recomenda adicionar um script às rotinas de inicialização de entrelaçamento:
Crie o arquivo com o comando
sudo nano /etc/network/if-pre-up.d/macchanger
neste arquivo, insira as linhas
#!/bin/sh
# Radomize the mac address for the given interface
/usr/bin/macchanger -r "$IFACE"
feche o arquivo, pressionando Ctrl + o e então Ctrl + x , e marque o arquivo como executável com o comando
chmod +x /etc/network/if-pre-up.d/macchanger
Este comando será então executado durante o processo de trazer a interface para cima, e atribuir um mac aleatório naquele momento.