This is what worked for me.
Remove all the ruby packages using synaptic: ALL of them
You need to install zlibc, zlib1g, zlib1g-dev, then recompile ruby.
e.g. sudo apt-get install zlibc etc.
THen install ruby-1.8.4 from source
Then download rubygems and install it.