Acabo de encontrarme con esto: http://www.high-on-it.co.za/2011/01/ubuntu-apt-get-update-binbzip2-returned.html Por lo que quizás la mejor solución sea ir cambiando de repositorio hasta encontrar con el funcione bien... De todas formas dudo mucho que la ingente cantidad de repositorios PPA no tenga nada que ver con tu problema.