Debian has introduced incremental updating of package lists. While in theory, this is a great feature, it is not always practical.

Incremental updates enable to download less data by fetching only the differences between the previous versions of the list. This results in significant savings concerning the amount of downloaded data.
The unfortunate downside is that a whole lot more fetches need to be done as each incremental update requires a server request. This becomes apparent when you don't often download package list updates, and there are suddenly a whole number of files waiting to be downloaded. The overhead of requesting each incremental slice separately causes the update to take more time than it would when downloading the whole list from scratch.

It is possible to enable the old "inefficient" system, where lists are downloaded in their entire by configuring APT to do so.

Disable pdiff downloads

To disable pdiff just for a session, run the update like so:

apt-get update -o Acquire::Pdiffs=false

To permanently disable pdiff, add the following to /etc/apt/apt.conf (if the file does not exist, create it):

Acquire::PDiffs "false";