Bem como você mesmo descobriu, todos os comandos apt-get install "alguma coisa" só funcionarão se você tiver na sua lista de repositórios o determinado pacote que você está querendo. Portanto não se trata de uma falha do comando, mas da sua lista de Repositórios. Você esqueceu de avisar o pessoal para depois que instalar isso comentar ou retirar essas linhas do repositório. Isso pode "quebrar" o seu sistema inteiro, não é aconselhável usar a lista do Debian Sid no lugar das do Ubuntu. Outra dica, você poderia ter usado a lista do Backports do 5.04, teria funcionado também e você não corre o risco de "quebrar" o seu sistema.
Abraços.