Can you try the following?:
1) sudo gedit /etc/network/interfaces
2) you should see the following:
auto eth0
iface eth0 inet dhcp
3) add a line with the new macadress right after the lines in step 2:
hwaddress ether 01:02:03:04:05:06
4) sudo /etc/init.d/networking restart
let me know if it works...