Você pode verificar se o seu endereço MAC realmente mudou usando ifconfig
e procurar o valor HWAddr
por trás do nome do dispositivo apropriado.
O que funcionou para mim no Mint, sem nenhum programa adicional para instalar, está usando o ifconfig:
sudo ifconfig eth0 down
sudo ifconfig eth0 hw ether 00:01:02:03:04:05
sudo ifconfig eth0 up
ou de forma mais permanente adicionando a linha:
hwaddress ether 00:01:02:03:04:05
em /etc/network/interfaces
, para que este MAC seja definido na inicialização.