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.