There is something wrong with my Kali VM and I cannot figure it out. Would you be able to offer some troubleshooting suggestions?

Simply put, it cannot conduct nmap scans with any degree of speed. It used to be fine, but since upgrading to Kali 2 it seems to have gone downhill.

For instance in my host machine I can nmap www.megacorpone.com and receive results in about 7 seconds. The same scan inside the VM is taking about 300+ seconds. Not acceptable!

What could be hindering the scan? The machine has plenty of RAM, and I the internet connection on the host machine seems fine.

Any ideas for troubleshooting this?