apt-get update very slow, stuck at "Waiting for headers"

I found a solution which helped me here: https://www.kubuntuforums.net/showthread.php?57567-Ubuntu-problems-on-update

You can let apt-get to regenerate lists cache using:

sudo apt-get clean
cd /var/lib/apt
sudo mv lists lists.old
sudo mkdir -p lists/partial
sudo apt-get clean
sudo apt-get update 

This sounds like it may be an issue with third party repos. I know Google's repo takes several minutes to respond here sometimes. If you have third party repos set up, open Update Manager, click Settings, then the "Other Software" tab. Uncheck all checkboxes, then hit close.

Now, fire up a terminal and use the following command and see if it is any better with the following command:

sudo apt-get update

If it is better, go back and enable each repo and recheck one by one until you find the problem repo.

If that does not work, you can have the update manager select the best main repos to use automatically. To do that, open Update Manager, then click Settings. Select the Ubuntu Software tab, then in the "Download from:" dropdown, select Other...

Now, in the window that pops up, click "Select Best Server"

It will then perform several tests to select the best server for you. Once it is completed, just click Choose Server.

Now, fire up the terminal and check again.