Last year I published an article on this blog about fixing update and upgrade issues in Kali Linux and it helped many users and now again after a year this issue has occurred which can not be solved by previous trick hence posting a new article here. Check previous article: http://com.puter.tips/2015/03/fix-updateupgrade-errors-in-kali-linux.html
This trick is better than previous one. All you need to do is check latest repository links and update it in your sources list. You can go to official Kali Linux website documents http://docs.kali.org/general-use/kali-linux-sources-list-repositories and check for the current repository.
Then open /etc/apt/sources.list in your favorite editor and overwrite the file with latest repositories links you found from official website.
For now you can gedit /etc/apt/sources.list and change it to as this is for latest version Kali Linux 2016.1 Rolling Release:
deb http://http.kali.org/kali kali-rolling main contrib non-free
# For source package access, uncomment the following line
# deb-src http://http.kali.org/kali kali-rolling main contrib non-free
That's it now you can run apt-get clean && apt-get autoremove && apt-get update && apt-get upgrade && apt-get dist-upgrade and it should work fine.