While installing a box, it happened that apt-get would segfault upon upgrade or install. Suspecting memory issues first, we tried quite a few things, before coming across a blogentry: a corrupt pkgcache was to blame. One should simply remove it and start over again:

cd /var/cache/apt rm pkgcache.bin srcpkgcache.bin

Unfortunately, we didn't save the corrupt files, so we cannot even open a bug.