apt-get update stuck on "Waiting for Headers" when using Windows XP ICS
Solution 1:
There seems to be a fundamental issue with the implementation of ICS and IP forwarding in general on Windows XP it simply cannot handle multiple connections to the same server, maybe it's some weird combination of a bug with intentional incompetence (as I like to call it), but the end result is that XP cannot function as a competent router/proxy for a linux system (maybe the limitations are intentionally put in place for non-windows systems).
It is interesting to note that this is not only limited to ICS. There is a hidden option in the windows registry that allows IP forwarding for network interfaces and it suffers from the same problem.
The only solution - it appears - is to either change the network topology to avoid using ICS (either connecting directly, or buying a dedicated switch/access point), or to use a different OS to set up the temporary bridge. I used an ubuntu live-cd (it wasn't my computer or it would have been running some *nix to begin with) and enabled packet forwarding and ip masquerading so the computer behaves as a bona-fide router.
Solution 2:
There are some rumours in the web (I can't verify them) about ICS problems with IP6. They said when ICS receives more than one IP6 connection it halts for a while. This could explain why wget works (only one connection), and apt-get update fails (lots of simultaneous connections).
You can try to disable IP6 in your server to test if this is the problem.
You can disable IP6 from the terminal with:
echo "#disable ipv6" | sudo tee -a /etc/sysctl.conf
echo "net.ipv6.conf.all.disable_ipv6 = 1" | sudo tee -a /etc/sysctl.conf
echo "net.ipv6.conf.default.disable_ipv6 = 1" | sudo tee -a /etc/sysctl.conf
echo "net.ipv6.conf.lo.disable_ipv6 = 1" | sudo tee -a /etc/sysctl.conf
Then reboot and check if you can update. If it works at least you know where the problem is. You can either disable IP6 permanent, or plan a new setup. Note that IP6 disabling will be a temporal hack, IP6 seems like unavoidable in the near future.
To enable IP6 back, delete the previous lines from /etc/sysctl.conf and reboot.