Acabo de buscarlo con synaptic, y si me aparece. Me deja marcarlo para instalarlo sin problemas.
Se me olvidaba, la versión que me aparece de bleachbit es la 0.9.2-2 -- www.LinuxCounter.net Registered user #558467 has 1 linux machines Registered Linux machine #2003003