We've had numerous reports on irc that making apt prefer gz is a better workaround for this issue (i.e. actually works, unlike some other things suggested above :) apt-get -o 'Acquire::CompressionTypes::Order::="gz"' update Or add this to /etc/apt/apt.conf : Acquire::CompressionTypes::Order:: "gz"; Ben