Como regenerar toda la cache de APT

Recientemente me he topado con un problema que, aunque no suele ser muy comun, si no se tiene idea puede resultar bastante dificil de resolver, ademas de que es bastante molesto.

Los sintomas del problema son fallos de segmentacion al realizar busquedas o instalaciones con apt/aptitude o desbordamientos de memoria en el caso de Synaptic o Adept, por lo que resulta imposible actualizar el sistema o instalar paquetes nuevos.

Tras pasar varios minutos siguiendo los fallos con strace, he llegado a la solucion, que es la siguiente.