I have solved my problem... I forgot to mention that I was running a VDS on UML - I have been informed that the stuff in /lib/tls does not work under uml, and as a result the immutable attribute had been set on the directory - stopping me from chmoding it. To solve it (if anyone else has a similar problem) do: chattr -i /lib/tls apt-get upgrade rm /lib/tls/*