Acho que resolvi esse problema. Vou esperar alguns dias e ter certeza.
Meu script quebrou o gerenciador de rede, eu acho. Eu adicionei o comando:
restart network-manager
Agora, quando me conecto, o endereço do Mac permanece alterado.
Acho que prefiro usar o wicd em vez disso.
O script completo, se alguém quiser usá-lo:
sudo ifconfig wlan0 down &&
sudo macchanger -A wlan0 &&
sudo ifconfig wlan0 up &&
sudo restart network-manager