Si instalas una versión antigua de Ubuntu te darás cuenta que los repositorios ya no existen, con lo cual no puedes instalar.
El truco es añadir estas líneas en el fichero /etc/apt/sources.list
deb https://old-releases.ubuntu.com/ubuntu/ CODENAME main restricted universe multiverse
deb https://old-releases.ubuntu.com/ubuntu/ CODENAME-updates main restricted universe multiverse
deb https://old-releases.ubuntu.com/ubuntu/ CODENAME-security main restricted universe multiverse
Donde CODENAME es tu versión (por ejemplo, natty).
Fuente.