Se você compartilhar seu /etc/apt/sources.list, provavelmente poderemos tentar ajudá-lo.
Caso contrário, escrevi uma ferramenta para depurar isso (presumo que você tenha rubygys e rubygems instalados):
server# gem install apt-repair-sources
...
server# apt-repair-sources
...
Isso deve informar quais linhas das suas fontes estão desativadas. Eu acho que é algo como, 11.04 foi movido de release.ubuntu.com para archive.ubuntu.com. Ou alguma coisa. Ou talvez um espelho que você está usando esteja inativo.