Depois de muita tentativa e erro, descobri que era algo (ainda não sei exatamente o quê) em .cache / software-center. Acho que devo denunciar, mas não sei para quem (idéias?). De qualquer forma, se alguém estiver interessado, avise-me e enviarei o infame diretório. Obrigado a todos que leram isto:)