Many times I’ve seen a VPS running such old versions of Ubuntu that they can no longer use apt at all because its no longer a supported release. For the most part at this stage, i fully recommend doing a reinstall of the machine which is the much easier faster solution. If for whatever reason this is not accepetable (its a server at a datacenter miles away kinda thing and not a VPS) this is what you do.
$ sudo vim /etc/apt/sources.list
and replace the repositories with:
deb http://old-releases.ubuntu.com/ubuntu/ $version main restricted
deb-src http://old-releases.ubuntu.com/ubuntu/ $version main restricted
deb http://old-releases.ubuntu.com/ubuntu/ $version-updates main restricted
deb-src http://old-releases.ubuntu.com/ubuntu/ $version-updates main restricted
deb http://old-releases.ubuntu.com/ubuntu/ $version universe multiverse
deb-src http://old-releases.ubuntu.com/ubuntu/ $version universe multiverse
deb http://old-releases.ubuntu.com/ubuntu $version-security main restricted
deb-src http://old-releases.ubuntu.com/ubuntu $version-security main restricted
Swapping out the $version for the actual version (ie edgy, intrepid etc) you currently have installed
Update your sources and install the upgrade tool with the following command.
$ sudo apt-get update && sudo apt-get upgrade && sudo apt-get install update-manager-core
Now run the upgrade:
$ sudo do-release-upgrade
The tool will run for a minute, then it may give you an error about your repositories saying they are invalid and would you like to update your repositories. Don’t answer yet. Open a new console and modify /etc/apt/sources.list
deb http://us.archive.ubuntu.com/ubuntu/ $newversion main restricted
deb-src http://us.archive.ubuntu.com/ubuntu/ $newversion main restricted
deb http://us.archive.ubuntu.com/ubuntu/ $newversion-updates main restricted
deb-src http://us.archive.ubuntu.com/ubuntu/ $newversion-updates main restricted
deb http://us.archive.ubuntu.com/ubuntu/ $newversion universe multiverse
deb-src http://us.archive.ubuntu.com/ubuntu/ $newversion universe multiverse
deb http://security.ubuntu.com/ubuntu $newversion-security main restricted
deb-src http://security.ubuntu.com/ubuntu $newversion-security main restricted
Then go back to the original prompt and choose y. The tool will then succeed. After your initial upgrade, simply running do-release-upgrade will suffice.
If you are going from one old-release to another expired release then you do not need to edit the sources.list in between.