gemを1.8にアップグレードする必要があります。それぞれのdebianパッケージをインストールしようとしましたが、アップグレードされていないようです
anujm@test:~$ dpkg -l |grep -i rubygem
ii rubygems 1.3.5-1ubuntu2 package management framework for Ruby libraries/applications
ii rubygems-lwes 0.8.2-1323277262 LWES rubygems
ii rubygems1.8 1.3.5-1ubuntu2 package management framework for Ruby libraries/applications
ii rubygems1.9 1.3.5-1ubuntu2 package management framework for Ruby libraries/applications
anujm@test:~$
anujm@test:~$ gem
gem gem1.8 gem1.9
anujm@test:~$ sudo gem1.8 install serve
ERROR: Error installing serve:
multi_json requires RubyGems version >= 1.3.6
anujm@test:~$
Rubygems-update をインストールする
gem install rubygems-update
update_rubygems
gem update --system
このコマンドを root として実行するか、sudo を使用します。