apt - Ubuntu 12.04 LTS server - build-essential install not possible

Have found this question multiple times on the forum, but none of the answers were serious enough.
So the problem with ubuntu 12.04. LTS server is that after a fresh install you can not install build-essential package.
This is what you get:

Reading package lists...
Building dependency tree...
Reading state information...
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:
The following packages have unmet dependencies:
 build-essential : Depends: libc6-dev but it is not going to be installed or
                            libc-dev
                   Depends: g++ (>= 4:4.4.3) but it is not going to be installed

Things that DON'T help:

apt-get clean
apt-get update
apt-get -f install
apt-get upgrade
dpkg --configure -a
apt-get autoclean
apt-get --fix-missing install build-essential

apt does say that I have "held broken packages", but none of the above commands solves them. After running any of the above commands the summary at the bottom is all zeros (upgraded, newly installed, remove, not upgraded)

uname -a gives:

Linux sorrg01lin 3.11.0-15-generic #25~precise1-Ubuntu SMP Thu Jan 30 17:42:40 UTC 2014 i686 i686 i386 GNU/Linux

lsb_release -a gives:

Distributor ID: Ubuntu
Description:    Ubuntu 12.04.4 LTS
Release:    12.04
Codename:   precise