Я некоторое время боролся с этим, обновившись до ruby 2.0.
Исправлено было установить nokigiri, используя apt-get
apt-get install ruby-nokogiri
В качестве примечания можно заметить, используя
$ gem dependency nokogiri
Gem nokogiri-1.6.1
hoe (~> 3.7, development)
hoe-bundler (>= 1.1, development)
hoe-debugging (>= 1.0.3, development)
hoe-gemspec (>= 1.0, development)
hoe-git (>= 1.4, development)
mini_portile (~> 0.5.0)
minitest (~> 2.2.2, development)
racc (>= 1.4.6, development)
rake (>= 0.9, development)
rake-compiler (~> 0.8.0, development)
rdoc (~> 4.0, development)
rexical (>= 1.0.5, development)