Eu mesmo resolvi o problema.
Faça o download do arquivo ISO e monte-o em uma pasta local:
wget http://old-releases.ubuntu.com/releases/jaunty/ubuntu-9.04-server-amd64.iso
mkdir cdrom
mount -o loop ubuntu-9.04-server-amd64.iso
Ajuste o /etc/apt/sources.list
e adicione a pasta local
deb file:///tmp/cdrom/ main
Execute uma atualização e instale update-manager-core
apt-get update
apt-get install update-manager-core
Agora, uma atualização do sistema de 9.04 para 9.10 e depois de 9.10 para 10.04 LTS funciona bem!