my 3 second guess is that you installed a binary package of ruby and
didn't install the dev package that includes the header files.. in
debian/ubuntu it's called ruby1.8-dev...
let me know if a "sudo apt-get install ruby1.8-dev" fixes your problems
-colin