Si tienes problemas con tus actualizaciones es por que seguramente no tienes actualizadas tus listas de repositorios. Hacerlo es muy fácil, sólo sigue las siguientes instrucciones:
Abre una terminal como administrador y escribe el siguiente comando:
nano /etc/apt/sources.list
Una vez abierto el editor escribe las siguientes lineas (o copia y pega):
deb http://http.kali.org/kali kali-rolling main non-free contrib
deb [arch=i386,amd64,armel,armhf] http://http.kali.org/kali kali-dev main contrib non-free
deb [arch=i386,amd64,armel,armhf] http://http.kali.org/kali kali-dev main/debian-installer
deb http://http.kali.org/kali kali main contrib non-free
deb-src http://http.kali.org/kali kali main contrib non-free
deb-src http://security.kali.org/kali-security kali/updates main contrib non-free
deb http://ppa.launchpad.net/ferramroberto/gsharkdown/ubuntu lucid main
deb http://www.deb-multimedia.org squeeze main non-free
deb http://download.virtualbox.org/virtualbox/debian yakkety contrib
Presionas "ctrl" + "o" para guardar.
Presionas "ctrl" + "x" para salir.
Ahora continua con tus actualizaciones.
Saludos...