Hola, más de alguna vez se deben haber topado con que querías cambiar tu dirección mac por algún problema... pero te topaste con que creías que no se podía...
Es muy fácil, debes bajar la interfaz de red:
sudo ifconfig eth0 down
luego:
ifconfig eth0 hw ether 00:00:00:00:00:01
Luego se revisa y levantas si se cambió:
sudo ifconfig eth0
sudo ifconfig eth0 up

Puede ser wifi o ethernet, depende como se llame tu interfaz, en mi caso me lanzaba un error al hacer el cambio, pero logré que cambiara sin dramas... tuve que hacer la misma operación unas 8 veces cambiando la mac de mi tarjeta, y al final funcionó sin mayores problemas...


acerca del error:
http://www.linuxforums.org/forum/linux-applications/20846-error-changing-mac-address-ifconfig-ethx-hw-ether-xx-xx-xx.html

recomendado para automático...
http://www.howtogeek.com/howto/ubuntu/change-your-network-card-mac-address-on-ubuntu/

Ejemplo práctico:

maximi89@Maximiliano:~$ sudo ifconfig eth0 down
maximi89@Maximiliano:~$ sudo ifconfig eth0
eth0 Link encap:Ethernet HWaddr 00:09:a1:82:42:33
inet addr:192.168.0.3 Bcast:192.168.0.255 Mask:255.255.255.0
BROADCAST MULTICAST MTU:1500 Metric:1
RX packets:2969599 errors:0 dropped:0 overruns:0 frame:0
TX packets:1965913 errors:42 dropped:0 overruns:0 carrier:0
collisions:15 txqueuelen:1000
RX bytes:3592112228 (3.3 GiB) TX bytes:221453006 (211.1 MiB)
Interrupt:18 Base address:0xac00

maximi89@Maximiliano:~$ sudo ifconfig eth0 hw ether 00:09:a1:82:42:32
maximi89@Maximiliano:~$ sudo ifconfig eth0
eth0 Link encap:Ethernet HWaddr 00:09:a1:82:42:32
inet addr:192.168.0.3 Bcast:192.168.0.255 Mask:255.255.255.0
BROADCAST MULTICAST MTU:1500 Metric:1
RX packets:2969599 errors:0 dropped:0 overruns:0 frame:0
TX packets:1965913 errors:42 dropped:0 overruns:0 carrier:0
collisions:15 txqueuelen:1000
RX bytes:3592112228 (3.3 GiB) TX bytes:221453006 (211.1 MiB)
Interrupt:18 Base address:0xac00

maximi89@Maximiliano:~$ sudo ifconfig eth0 up


Buena suerte!