Comment 32 for bug 336736

There is a more elegant workaround which allows to run macchanger before network-manager is started and doesn't require /etc/init/network-manager.conf to be modified (which could cause problems on upgrades).

Simply create /etc/init/macchanger.conf with the following contents (without the "snip" lines):
--------------------snip--------------------
# macchanger - set MAC addresses
#
# Set the MAC addresses for the network interfaces.

description "change mac addresses"

start on starting network-manager

pre-start script
        /usr/bin/macchanger -e wlan0
        /usr/bin/macchanger -e eth0
        /usr/bin/macchanger -e wmaster0
        /usr/bin/macchanger -e pan0
        #/usr/bin/logger wlan0 `/usr/bin/macchanger -s wlan0`
        #/usr/bin/logger eth0 `/usr/bin/macchanger -s eth0`
end script
--------------------snip--------------------

upstart will then make sure that the script is run before network-manager is started (that's what the "starting network-manager" line is about).

This helped me, because the workaround by editing /etc/network/interfaces didn't work for me, so hopefully this helps others too!