I was experiencing extremely slow gem updates on my Slicehost VPS. gem would max out the memory usage and sit there, doing a bulk update on the index but never actually updating.
After a few attempts at a server software upgrade, I found success with the following commands.
gem1.8 update --system --source http://segment7.net/
gem1.8 update --no-rdoc --no-ri
I don't think the first command really helped, but I mention it because I did run it tonight. The second command issues the update, but without downloading the rubygems docs, etc. This sped things up, though the whole process still took about 30 minutes.