The default mirror for machine installed around Nova Scotia is sometime doing wierd things. Switching to another server seems to do the trick. I recommend U Waterloo's repository at http://mirror.csclub.uwaterloo.ca/. To change this:
- backup /etc/apt/sources.list
- replace http://ca.ubuntu.[...] by another server name such as http://mirror.csclub.uwaterloo.ca/ .
- Save the file
- type sudo apt-get update
A list of mirror is available here: https://launchpad.net/ubuntu/+archivemirrors