Você precisará verificar suas fontes. Eu vejo que libruby1.8 1.8.7.352-2 está disponível através de main , embora pareça que a versão mais nova que você tem é: 1.8.6.111-2ubuntu1 . Isso provavelmente significa que você dist-upgrade falhou ou que ainda precisa update de suas fontes.
$ apt-cache policy libruby1.8
libruby1.8:
Installed: 1.8.7.352-2
Candidate: 1.8.7.352-2
Version table:
*** 1.8.7.352-2 0
500 http://archive.ubuntu.com/ubuntu/ oneiric/main amd64 Packages
100 /var/lib/dpkg/status