I had the same problem but fixed it. It appears that dpkg doesn't finish before the VM restarts so you have to manually do it.
- When you bootup, at GRUB, type 'e' and add 'init=/bin/bash' at the end of the line that starts with 'linux'.
- The line on my VM before edit:
- linux /boot/vmlinuz-4.6.0-kali1-amd64 root=UUID=some_unique_hex_string_here ro initrd=/install/initrd.gz quiet
- The line on my VM after edit:
- linux /boot/vmlinuz-4.6.0-kali1-amd64 root=UUID=some_unique_hex_string_here ro initrd=/install/initrd.gz quiet init=/bin/bash
- Hit F10
- At the command line enter each of these commands:
- su
- mount -o remount,rw /dev/sda1 / (Or wherever your root partition is)
- dpkg --configure -a
You may need an internet connection first, and if you do, you want to apt-get update/upgrade from the terminal here.
Hope that helps!