So "halt -p" stopped working for me. The same issue has occurred when I use a live disk. I have since reinstalled Kali 2.0 and the problem occurs less often, but It still does. I try to be consistent and I kill all active programs then try shutting it down. It seems to work as long as I hope and think in my head "please work, please work, please work".

All jokes aside, there is nothing I can see outright that is different about each time I shutdown, restart or log off. Occasionally, the system hangs and never shuts down. (It seems to be after killing everything first).