Cannot install "ATI/AMD proprietary FGLRX graphics driver" (SystemError)

Question

I have just installed a fresh copy of 12.04.1 64bit. I formatted my PC completely and enabled updates during the installation. After the installation was complete, I went on updating my software.

However, when I wanted to install the additional drivers using the Additional Drivers tool (namely "ATI/AMD proprietary FGLRX graphics driver"), it gave me this error:

SystemError: E:Unable to correct problems, you have held broken packages.

The same error shows up if I try installing the post-release updates driver.

Installing the drivers from the terminal results in this output:

XXXXXX:~$ sudo apt-get install fglrx
[sudo] password for XXXXX:
Reading package lists... Done
Building dependency tree
Reading state information... Done
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:
fglrx : Depends: lib32gcc1 but it is not going to be installed
Depends: libc6-i386 but it is not going to be installed
E: Unable to correct problems, you have held broken packages."

I get this using sudo apt-get update: http://pastebin.com/AWAtDXjY

But sudo apt-get install fglrx still get me this error: http://pastebin.com/RYM55bVN

&

sudo apt-get -f install fglrx gives me this error: http://pastebin.com/xxekajvP

Any help would be greatly appreciated.

(Please note that I'm new to Linux, coming directly from Windows. I have tried Ubuntu twice or so before, but it was not for a long period of time. The drivers got installed smoothly the few times I've tried Ubuntu, but post-release updates never worked for me.)

[I am going to work now, so I can only answer from my phone. Can't really test any new solutions you may give me until ~10 hours from now on. Maybe more.]

@stonedsquirrel

When I try to run that command, I get this error:

XXXXXX:~$ sudo apt-get install fglrx
[sudo] password for XXXXX: 
Reading package lists... Done
Building dependency tree 
Reading state information... Done
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: 

    fglrx : Depends: lib32gcc1 but it is not going to be installed

             Depends: libc6-i386 but it is not going to be installed

E: Unable to correct problems, you have held broken packages."
ie. I get the same error.