The short answer: Updated your package sources.

The default install of Ubuntu does some basic package source modification based on your language and location. For me, this meant that my package source for all of my packages was us.archive.ubuntu.com. This is a very commonly used repository, and most likely isn't anywhere near you. I highly recommend you change this to a repository closer to you. You can find one using this mirror list from Canonical.

I used to simply jump into a graphic editor like Kate, or a command line editor like Vi (vim) to make this change. The problem with this is that it is slow, you have to run the editor, jump to each line containing the string, edit it, and save when I'm done. This can still take minutes if you have a find a replace feature. It took me a couple tries, but memorizing the following command has made my life easier. This command uses sed to edit the file in place, and to do a find and replace, all using only a single command.

Before running this command, package upgrades took 5-10 minutes for a medium sized set. The transfer was around 140kB/s from the standard US archive. After switching my package sources and updating, I was able to get my upgrades at a rate of 1500-2000kB/s, which is over 1000% faster.