I've had bad luck with Debian's Ruby packages. First thing I do when I build a new ubuntu server is pull down a fresh copy of the ruby source from ruby-lang.org and compile it. Then I install rubygems and rails.
It seems to me that you're having more issues just trying to get up and running with Rails than you are deploying applications, which is an entirely different monster all together.
Here's a method of installing rails that I know from experience works on debian/ubuntu: http://blog.fiveruns.com/2008/3/3/compiling-ruby-rubygems-and-rails-on-ubuntu
I'd get rid of all of the debian ruby/rails packages that you have first, then use the method in the blog post I linked to. I'd install ruby 1.8.7 instead of 1.8.6 that's mentioned in the blog though.
