Unable to install Rails using RVM on Ubuntu 12.04 LTS

Question

I am using Ubuntu 12.04 LTS x86_64 Minimal and I have installed Ruby and RVM according to these instructions. Ruby installs fine, and RVM installs fine and works perfectly.

I have visited just about every SO question I can find, and article on this issue and nothing has worked. Rails still won't install, and I am unable to do anything to get it to work thus far.

gem install rails -v 4.0.0 returns either 'success' (it returns nothing, and rails remains unusable) or fails giving:

[ tsujp ~ 437 / 24 / 1 ] $ gem install rails -v 4.0.0
Building native extensions.  This could take a while...
ERROR:  Error installing rails:
    ERROR: Failed to build gem native extension.

    /home/tsujp/.rvm/rubies/ruby-2.0.0-p353/bin/ruby extconf.rb

Gem files will remain installed in /home/tsujp/.rvm/gems/ruby-2.0.0-p353/gems/atomic-1.1.14 for inspection.
Results logged to /home/tsujp/.rvm/gems/ruby-2.0.0-p353/gems/atomic-1.1.14/ext/gem_make.out

I have checked all folders in ~/.rvm for gems relating to rails, and nothing.

Gem Environment

[ tsujp gems 451 / 39 / 0 ] $ gem environment
RubyGems Environment:
  - RUBYGEMS VERSION: 2.1.11
  - RUBY VERSION: 2.0.0 (2013-11-22 patchlevel 353) [x86_64-linux]
  - INSTALLATION DIRECTORY: /home/tsujp/.rvm/gems/ruby-2.0.0-p353
  - RUBY EXECUTABLE: /home/tsujp/.rvm/rubies/ruby-2.0.0-p353/bin/ruby
  - EXECUTABLE DIRECTORY: /home/tsujp/.rvm/gems/ruby-2.0.0-p353/bin
  - SPEC CACHE DIRECTORY: /home/tsujp/.gem/specs
  - RUBYGEMS PLATFORMS:
    - ruby
    - x86_64-linux
  - GEM PATHS:
     - /home/tsujp/.rvm/gems/ruby-2.0.0-p353
     - /home/tsujp/.rvm/gems/ruby-2.0.0-p353@global
  - GEM CONFIGURATION:
     - :update_sources => true
     - :verbose => true
     - :backtrace => false
     - :bulk_threshold => 1000
  - REMOTE SOURCES:
     - https://rubygems.org/
  - SHELL PATH:
     - /home/tsujp/.rvm/gems/ruby-2.0.0-p353/bin
     - /home/tsujp/.rvm/gems/ruby-2.0.0-p353@global/bin
     - /home/tsujp/.rvm/rubies/ruby-2.0.0-p353/bin
     - /home/tsujp/.rvm/bin
     - /usr/local/sbin
     - /usr/local/bin
     - /usr/sbin
     - /usr/bin
     - /sbin
     - /bin
     - /usr/games
     - /usr/lib/postgresql/9.1/bin
     - /home/tsujp

Gem List:

[ tsujp gems 452 / 40 / 0 ] $ gem list

*** LOCAL GEMS ***

bigdecimal (1.2.0)
bundler (1.3.5)
bundler-unload (1.0.2)
executable-hooks (1.2.6)
i18n (0.6.5)
io-console (0.4.2)
json (1.7.7)
minitest (4.3.2)
multi_json (1.8.2)
psych (2.0.0)
rake (0.9.6)
rdoc (4.0.0)
rubygems-bundler (1.4.2)
rvm (1.11.3.8)
test-unit (2.0.0.0)
tzinfo (0.3.38)

$PATH:

[ tsujp gems 453 / 41 / 0 ] $ echo $PATH
/home/tsujp/.rvm/gems/ruby-2.0.0-p353/bin:/home/tsujp/.rvm/gems/ruby-2.0.0-p353@global/bin:/home/tsujp/.rvm/rubies/ruby-2.0.0-p353/bin:/home/tsujp/.rvm/bin:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games:/usr/lib/postgresql/9.1/bin:/home/tsujp

RVM RUBIES:

[ tsujp gems 454 / 42 / 0 ] $ rvm list rubies

rvm rubies

=* ruby-2.0.0-p353 [ x86_64 ]

# => - current
# =* - current && default
#  * - default

I am really out of ideas what to do, I cannot deploy my application without rails...