I've been running a VM of Kali Linux 2.0 on my local machine for about an year now. It's been a great learning experience and I've used a lot of the programs in Kali to assist in expanding my security knowledge.
I noticed that the updates were failing in my VM the last few weeks. At first I just assumed there was a network / internet issue. However, I continued to receive errors like the following:
err http://http.kali.org kali/main sources 404 not found
After doing some Googling, I found that a new version of Kali was released. (Shame on me for not keeping up with this. I added Kali.org to feedly). Rather than downloading the VM again, I decided to look into upgrading the VM instead.
The blog post here has very detailed instructions on how to do this. I ran the code. It took quite a while to upgrade. I left it upgrading and came back in the morning to a new and improved Kali experience.