When I try to install gcc on Ubuntu 12.04 LTS Server with apt-get install gcc, I get the following error:

The following packages have unmet dependencies:
 gcc : Depends: cpp (>= 4:4.6.1-2ubuntu5) but it is not going to be installed
       Depends: gcc-4.6 (>= 4.6.1-1) but it is not going to be installed
       Recommends: libc6-dev but it is not going to be installed or
                   libc-dev

When I delve deeper (i.e. try to apt-get install gcc-4.6), I get:

 gcc-4.6 : Depends: gcc-4.6-base (= 4.6.1-9ubuntu3) but 4.6.3-1ubuntu5 is to be installed
           Depends: cpp-4.6 (= 4.6.1-9ubuntu3) but it is not going to be installed
           Depends: libgomp1 (>= 4.6.1-9ubuntu3) but it is not going to be installed
           Depends: libquadmath0 (>= 4.6.1-9ubuntu3) but it is not going to be installed
           Recommends: libc6-dev (>= 2.13-0ubuntu6) but it is not going to be installed

So when I try to install gcc-4.6=4.6.1-9ubuntu3 I get a list of 366 packages to remove (including e.g. apt). Which is craziness.

This is an essentially vanilla installation of Ubuntu 12.04 LTS Server (i.e. I installed nginx, python-flup, python-yaml, rsync, python-pkg-resources, lsof, fontconfig, iptables, ufw, scons, and grc).

It is very surprising to me that I cannot install gcc, so I am somewhat confused as to why attempting to install gcc fails. The only apparent fix would seem to be uninstalling 366 packages, many of which are central to the operation of Ubuntu.

Something doesn't add up, and I would be very grateful for assistance.

EDIT The above is with the latest packages of course, having used apt-get update; apt-get upgrade before attempting the above. Sorry, I should have mentioned that.