Se o Synaptic estiver dizendo que o pacote não está instalado, provavelmente ele não é ou possivelmente foi removido. Para instalá-lo, faça
sudo apt-get install rails
ou apenas clique com o botão direito no pacote no Synaptic e clique em "Instalar".