O problema é bem simples! Basta observar as mensagens.
libbz2-1.0 depende de libc6 (>= 2.5-0ubuntu1); porém:
Versão de libc6 no sistema é 2.3.6-0ubuntu20.
Para instalar o Gnome você vai precisar instalar o pacote libbz2. Para instalar o libbz2 você irá precisar instalar a versão mais recente do pacote libc6. Provavelmente, para instalar o pacote libc6 você irá precisar atualizar outro pacote e assim por diante.
Como já falaram, é muito melhor atualizar para o Edgy.
Boa sorte!