Eu não posso testar isso, já que estou no Oneiric e essa versão já tem mais de 300, mas você pode tentar procurar por PPAs usando: link (às vezes é um pouco lento).
Já tentei uma pesquisa rápida para "ruby1.8 lucid" :
-
Redmine PPA por exemplo contém
ruby1.8 1.8.7.357-1~lucid+2
Tenha cuidado ao usar os PPAs, precauções gerais se aplicam.