Compiling passenger-install-nginx-module; "C compiler gcc is not found"

I am in the middle of a process of installing Redmine served with passenger and nginx with this tutorial. With the passenger-install-nginx-module, it works fine and during compiling it outputs an error with this,

Compiling and installing Nginx...
# sh ./configure --prefix='/etc/nginx' --with-http_ssl_module --with-http_gzip_static_module --with-cc-opt='-Wno-error' --with-pcre='/tmp/root-passenger-3197/pcre-8.31' --add-module='/var/lib/gems/1.8/gems/passenger-3.0.18/ext/nginx'
checking for OS
 + Linux 3.2.0-32-generic-pae i686
checking for C compiler ... not found

./configure: error: C compiler gcc is not found

--------------------------------------------

It looks like something went wrong

I don't understand why it cannot find gcc, but in the precheck step it said that gcc is found,

Checking for required software...

 * GNU C++ compiler... found at /usr/bin/g++
 * The 'make' tool... found at /usr/bin/make
 * A download tool like 'wget' or 'curl'... found at /usr/bin/wget
 * Ruby development headers... found
 * OpenSSL support for Ruby... found
 * RubyGems... found
 * Rake... found at /usr/bin/rake
 * rack... found
 * Curl development headers with SSL support... found
 * OpenSSL development headers... found
 * Zlib development headers... found

I then apt-get the possible gcc packages, but none were installed/updated because I already have them.

EDIT:

Packages I've tried with gcc,

gcc-4.4 g++-4.4 libstdc++6-4.4-dev gcc

EDIT:

nginx block for the redmine,

server {

    server_name         redmine.domain.com;

    access_log          /var/www/redmine.access.log;
    error_log           /var/www/redmine.error.log;

    root                /var/www/domain.com/redmine/public;

    passenger_enabled   on;
}

EDIT:

Now it looks like the issue is something to do with passenger_root and passenger_ruby, although I have included it in the nginx.conf now, but I'm not certain if they are the correct paths (what could I do to find the correct ones?)

My nginx.conf

user www-data;
worker_processes 4;
pid /var/run/nginx.pid;

events {
    worker_connections 768;
    # multi_accept on;
}

http {

    ##
    # Basic Settings
    ##

    sendfile on;
    tcp_nopush on;
    tcp_nodelay on;
    keepalive_timeout 65;
    types_hash_max_size 2048;
    server_tokens off;

    # server_names_hash_bucket_size 64;
    # server_name_in_redirect off;

    include /etc/nginx/mime.types;
    default_type application/octet-stream;

    ##
    # Logging Settings
    ##

    access_log /var/log/nginx/access.log;
    error_log /var/log/nginx/error.log;

    ##
    # Gzip Settings
    ##

    gzip on;
    gzip_disable "msie6";

    # gzip_vary on;
    # gzip_proxied any;
    # gzip_comp_level 6;
    # gzip_buffers 16 8k;
    # gzip_http_version 1.1;
    # gzip_types text/plain text/css application/json application/x-javascript text/xml application/xml application/xml+rss text/javascript;

    ##
    # nginx-naxsi config
    ##
    # Uncomment it if you installed nginx-naxsi
    ##

    #include /etc/nginx/naxsi_core.rules;

    ##
    # nginx-passenger config
    ##
    # Uncomment it if you installed nginx-passenger
    ##

    #passenger_root /usr;
    #passenger_ruby /usr/bin/ruby;

    passenger_root /var/lib/gems/1.8/gems/passenger-3.0.18;
    passenger_ruby /usr/bin/ruby1.8;

    ##
    # Virtual Host Configs
    ##

    include /etc/nginx/conf.d/*.conf;
    include /etc/nginx/sites-enabled/*;
}


#mail {
#   # See sample authentication script at:
#   # http://wiki.nginx.org/ImapAuthenticateWithApachePhpScript
# 
#   # auth_http localhost/auth.php;
#   # pop3_capabilities "TOP" "USER";
#   # imap_capabilities "IMAP4rev1" "UIDPLUS";
# 
#   server {
#       listen     localhost:110;
#       protocol   pop3;
#       proxy      on;
#   }
# 
#   server {
#       listen     localhost:143;
#       protocol   imap;
#       proxy      on;
#   }
#}

How would I fix this issue?