O primeiro conjunto de comandos está próximo. O erro que você está vendo é porque o seu wlan0 ainda está ativo.
sudo service network-manager stop && sudo ifconfig wlan0 down && sudo macchanger -a wlan0 && sudo ifconfig wlan0 up && sudo service network-manager start
Em um mundo perfeito, isso deve funcionar como esperado, mas o network-manager redefine o mac na inicialização em 16.04. Parece que isso é um problema com o network-manager e parece que eles estão cientes. bugs.launchpad.net