I am trying to compile a C program on Ubuntu precise 12.04. Here's the program:

#include <stdio.h>

int main(int argc, char** argv) {
  printf("Hello World!");
  return 0;
}

My gcc version is 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5). Initially it did not find cc1 so I added a soft link. Now I get this message when I try to compile:

gcc: internal compiler error: Segmentation fault (program cc1)

Compiling the same program with g++ works fine.

I tried reinstalling build-essential, but to no avail. What am I missing?

EDIT: I tried reinstalling according to @gertyvdijk's suggestion. As it did not help, here is the output of apt-cache policy gcc-4.6:

  gcc-4.6:  Installed: 4.6.3-1ubuntu5
  Candidate: 4.6.3-1ubuntu5
  Version table:
 *** 4.6.3-1ubuntu5 0
        500 http://il.archive.ubuntu.com/ubuntu/ precise/main amd64 Packages
        100 /var/lib/dpkg/status

and the output of ls -l /usr/bin/gcc:

lrwxrwxrwx 1 root root 7 Mar 13  2012 /usr/bin/gcc -> gcc-4.6

EDIT #2: here's a verbose compiler output:

    gcc -v aaa.c 
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.6/lto-wrapper
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro 4.6.3-1ubuntu5' --with-bugurl=file:///usr/share/doc/gcc-4.6/README.Bugs --enable-languages=c,c++,fortran,objc,obj-c++ --prefix=/usr --program-suffix=-4.6 --enable-shared --enable-linker-build-id --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.6 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-gnu-unique-object --enable-plugin --enable-objc-gc --disable-werror --with-arch-32=i686 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5) 
COLLECT_GCC_OPTIONS='-v' '-mtune=generic' '-march=x86-64'
 /usr/lib/gcc/x86_64-linux-gnu/4.6/cc1 -quiet -v -imultilib . -imultiarch x86_64-linux-gnu aaa.c -quiet -dumpbase aaa.c -mtune=generic -march=x86-64 -auxbase aaa -version -fstack-protector -o /tmp/ccHfcXMs.s
gcc: internal compiler error: Segmentation fault (program cc1)
Please submit a full bug report,
with preprocessed source if appropriate.
See <file:///usr/share/doc/gcc-4.6/README.Bugs> for instructions.