Eu não executo mais nenhuma caixa 8.04, mas parece que você precisa ter o gcc-4.3 instalado antes de permitir que você continue. Você obtém algum resultado de "apt-cache search gcc-4.3" ou "sudo apt-get install gcc-4.3"?
O que seus arquivos /etc/apt/sources.list e /etc/apt/sources.list.d/* contêm? Você tem universo ou multiverso assim como o principal listado? Você tem o backports repo habilitado também?
Dando uma olhada rápida em alguns dos arquivos Package.gz para hardy eu não vi nada para o gcc-4.3, mas eu não olhei muito longe porque eu não sei quais repos e dists você está usando.
Boa sorte