Comment 8 for bug 193574

With the bzip errors, try running sudo apt-get update and then sudo apt-get upgrade. Hopefully it will go away.

If it doesn't once you get into gutsy and *still* have a bzip error with gutsy security then you cna try commenting out the gutsy security entry in /etc/apt/sources.list, running sudo apt-get update, and then uncommenting it and running sudo apt-get update.

We can never promise clean installs when you have installed software from 3rd party repositories, as you have from the error messages you've posted.