No connection on wired network after MAC change

OS: Kali Linux 2016.2 AMD64 on VirtualBox
NIC: Realtek PCIe FE Family Controller

After changing my MAC address using macchanger, my network manager reads "Wired Connecting", but never connects.
I have tried every combination of start/stop/restart/up/down with both network-manager.service and ifconfig eth0.
I have also tried using the -a, -A, and -r options with macchanger, as well as doing all of these options before and after a system reboot
I am successfully changing the MAC address, but I am unable to connect to any websites using Firefox.

I have even gone as far as having the MAC address changed on boot before network-manager.service starts.

**Note**
If I use "macchanger -p eth0" to reset to the burned in MAC address, the change is also successful and network manager automatically connects without a restart.