This work is licenced under a Creative Commons Licence.
Unfortunately I didn't do a full debug of the problem, but I had problems where both apt-get and aptitude were dying when run. Further investigation lead me to notice segmentation faults in my logs, for example:
May 1 18:34:57 ebony kernel: [249491.980426] apt-get: segfault at 7f2b59c95474 ip 00007f2b56d9bf37 sp 00007fff4401aa80 error 4 in libapt-pkg.so.4.10.1[7f2b56d4f000+10a000]
This was fixed as follows:
sudo rm /var/cache/apt/*.bin