I came across with this problem a few days ago after updating Kali — I use Kali Linux 2016.2 (64 bit), by the way. Before updating/upgrading the system through its repositories, macchanger was working like a charm. However, soon after the update, I tried to spoof my MAC address in order to bypass some MAC filtering I've set up in my own network, and everytime I attempted to do it (and there were several tries…), my MAC address was automatically reverted to, or its permanent burnt-in address, or a random one.
At first, I was not sure about what could be possibly causing it, but after doing some tests, using different devices, tools and setups, I found out that the issue was being originated by NetworkManager, which I realized later being not an issue exactly, but just a different default configuration of the service than the one we were used to.
The lastest versions of NetworkManager, 1.4.2, in this particular case, implement several configuration options for MAC spoofing/cloning, and when put in use, these options tend to override any configurations set by tools like macchanger and macchito, making them practically useless. It turns out that, in its newer versions (above 1.2, but more notably the versions above 1.4, which dispenses wpa_supplicant support for this purpose), NetworkManager default configurations are set to randomize your MAC address or revert it to the permanent one at the moment your interface scans the networks around you or attempt to connect into one of them. This new feature is very interesting for purposes of anonymity; for MAC spoofing, however, it can complicate the authentication process.

Disabling this feature is very simple, you'll just need to change some NetworkManager's configurations. You can do this either by editing /etc/NetworkManager/NetworkManager.conf file or adding an additional .conf file to /etc/NetworkManager/conf.d directory (the .conf file can have any name). Though I highly recommend the second option, given that when updated, NetworkManager usually replaces its main .conf file, and if you choose the first option, your saved options may be overriten when the service gets these updates from time to time.

Whatever option you choose, in the text editor, add the following lines:

Then save the file, and inside the terminal, restart NetworkManager by typing in:
service network-manager restart
And it's done, the problem now should have been resolved.
If you want to know more about how can you configure NetworkManager in its newer versions by yourself, I recommend reading the following article, it was the one that helped me into solving this:
In addition, the GNOME Developer Center offers a reference manual for making changes in the newer versions of NetworkManager, you may find it very helpful as well: