I had this issue where I could not install anything new in my Ubuntu server. After some searching I come to lean that the packages cache seemed to be corrupted
# symptom is something such as this
root@media:~# apt-get update
root@media:~# apt-get install htop
Reading package lists… Done
Segmentation faulty tree… 50%
# and this is what fixed the problem
# you need to be as root or su into root
sudo rm /var/cache/apt/*.bin
I am happy again.