`require': no such file to load -- mkmf (LoadError)

I was trying to install rails on Ubuntu Natty Narwhal 11.04, using ruby1.9.1. I installed ruby using apt-get install ruby1.9.1-full which contains the dev package. I googled the error and all have suggested I install the 1.9.1-dev which I already have. Building native extensions. This could take a while... ERROR: Error installing rails: ERROR: Failed to build gem native extension. /usr/bin/ruby1.8

[yuiseki]

sudo aptitude install ruby1.9.1-dev